How to solve this Pell's equation $x^{2} - 991y^{2} = 1 $
If $x^2-991y^2=1$, then we have that $$ \begin{align} \left(\frac{1}{y}\right)^2 &=\left(\frac{x}{y}\right)^2-991\\ &=\left(\frac{x}{y}-\sqrt{991}\right)\left(\frac{x}{y}+\sqrt{991}\right)\tag{1} \end{align} $$ Since $\frac{x}{y}\stackrel{.}{=}\sqrt{991}\stackrel{.}{=}31.5$, we get that $$ \left|\frac{x}{y}-\sqrt{991}\right|\stackrel{.}{=}\frac1{63}\frac1{y^2}\tag{2} $$ As described in Section $5$ of this paper, to get a rational approximation as close as $(2)$, $\dfrac{x}{y}$ must be a convergent of the continued fraction for $\sqrt{991}$. Since the next continuant, c_n, satisfies $$ \frac1{c_n+2}\frac1{y^2}\lt\left|\frac{x}{y}-\sqrt{991}\right|\le\frac1{c_n}\frac1{y^2}\tag{3} $$ the next continuant should be within about $1$ of $62$.
The continued fraction for an algebraic number of degree $2$ will eventually repeat. The continued fraction for $\sqrt{991}$ is $$ (31, [2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2, 62]) $$ where the sequence in brackets repeats.
The only continuant within $1$ of $62$ is the $62$. Thus, the first positive solution corresponds to the rational approximation to $\sqrt{991}$ with the continued fraction $$ (31, 2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2) $$ which is $$ \color{#C00000}{\frac{x_1}{y_1}}=\color{#C00000}{\frac{379516400906811930638014896080}{12055735790331359447442538767}}\tag{4} $$ The next solution comes from the next time the next continuant is $62$; that is, for the rational approximation to $\sqrt{991}$ with the continued fraction $$ (31, 2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2, 62, 2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2) $$ which is $$ \color{#C00000}{\frac{x_2}{y_2}}=\color{#C00000}{\frac{288065397114519999215772221121510725946342952839946398732799}{9150698914859994783783151874415159820056535806397752666720}}\tag{5} $$ We can get all the solutions, starting with $(x_0,y_0)=(1,0)$ and $(4)$, using $$ \begin{align} x_n&=759032801813623861276029792160\,x_{n-1}-x_{n-2}\\ y_n&=759032801813623861276029792160\,y_{n-1}-y_{n-2} \end{align}\tag{6} $$
Edit, 6 April 2014: I put some GMP oversize integers in two of my indefinite forms programs in C++, so here is the Lagrange cycle method for doing this. The importance of this is that no decimal accuracy is required at all, and no pattern recognition (cycle detection??), no memory is required at all.
Pell 991
0 form 1 62 -30 delta -2
1 form -30 58 5 delta 12
2 form 5 62 -6 delta -10
3 form -6 58 25 delta 2
4 form 25 42 -22 delta -2
5 form -22 46 21 delta 2
6 form 21 38 -30 delta -1
7 form -30 22 29 delta 1
8 form 29 36 -23 delta -2
9 form -23 56 9 delta 6
10 form 9 52 -35 delta -1
11 form -35 18 26 delta 1
12 form 26 34 -27 delta -1
13 form -27 20 33 delta 1
14 form 33 46 -14 delta -3
15 form -14 38 45 delta 1
16 form 45 52 -7 delta -8
17 form -7 60 13 delta 4
18 form 13 44 -39 delta -1
19 form -39 34 18 delta 2
20 form 18 38 -35 delta -1
21 form -35 32 21 delta 2
22 form 21 52 -15 delta -3
23 form -15 38 42 delta 1
24 form 42 46 -11 delta -4
25 form -11 42 50 delta 1
26 form 50 58 -3 delta -20
27 form -3 62 10 delta 6
28 form 10 58 -15 delta -4
29 form -15 62 2 delta 31
30 form 2 62 -15 delta -4
31 form -15 58 10 delta 6
32 form 10 62 -3 delta -20
33 form -3 58 50 delta 1
34 form 50 42 -11 delta -4
35 form -11 46 42 delta 1
36 form 42 38 -15 delta -3
37 form -15 52 21 delta 2
38 form 21 32 -35 delta -1
39 form -35 38 18 delta 2
40 form 18 34 -39 delta -1
41 form -39 44 13 delta 4
42 form 13 60 -7 delta -8
43 form -7 52 45 delta 1
44 form 45 38 -14 delta -3
45 form -14 46 33 delta 1
46 form 33 20 -27 delta -1
47 form -27 34 26 delta 1
48 form 26 18 -35 delta -1
49 form -35 52 9 delta 6
50 form 9 56 -23 delta -2
51 form -23 36 29 delta 1
52 form 29 22 -30 delta -1
53 form -30 38 21 delta 2
54 form 21 46 -22 delta -2
55 form -22 42 25 delta 2
56 form 25 58 -6 delta -10
57 form -6 62 5 delta 12
58 form 5 58 -30 delta -2
59 form -30 62 1 delta 62
60 form 1 62 -30
disc 3964
Automorph, written on right of Gram matrix:
5788591406539787767296194303 361672073709940783423276163010
12055735790331359447442538767 753244210407084073508733597857
Pell automorph
379516400906811930638014896080 11947234168218377212415555918097
12055735790331359447442538767 379516400906811930638014896080
Pell unit
379516400906811930638014896080^2 - 991 * 12055735790331359447442538767^2 = 1
=========================================
991 991
I give a complete description at How to detect when continued fractions period terminates and at the MO question I link to there. You need to be very confident about using two by two matrices. However, and this is the key point, it is NOT NECESSARY to use high decimal precision. All is integer arithmetic. The only approximation is the integer part of the square root of the discriminant, as in $\left\lfloor \sqrt {3964} \right\rfloor = 62.$ The bad news is that my program is limited to number s below $2^{31},$ so the "answer" at the end was gibberish and I just erased it. Oh, this comes up sometimes...with this method, it is also not necessary to use any cycle detection. The cycle for $991$ begins with the binary form $\langle 1,62,-30 \rangle$ and ends precisely when we, once again, reach $\langle 1,62,-30 \rangle.$ Not before, not after. I have a short example, the triples may repeat the first entry, in this case 9, but you are done when all three entries match:
0 form 9 75 -16 delta -4
1 form -16 53 53 delta 1
2 form 53 53 -16 delta -4
3 form -16 75 9 delta 8
4 form 9 69 -40 delta -1
5 form -40 11 38 delta 1
6 form 38 65 -13 delta -5
7 form -13 65 38 delta 1
8 form 38 11 -40 delta -1
9 form -40 69 9 delta 8
10 form 9 75 -16
Let me start with an easier one, 91, where I do get an answer, then show 991 after:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell
91
0 form 1 18 -10 delta -1
1 form -10 2 9 delta 1
2 form 9 16 -3 delta -5
3 form -3 14 14 delta 1
4 form 14 14 -3 delta -5
5 form -3 16 9 delta 1
6 form 9 2 -10 delta -1
7 form -10 18 1 delta 18
8 form 1 18 -10
disc 364
Automorph, written on right of Gram matrix:
89 1650
165 3059
Pell automorph
1574 15015
165 1574
Pell unit
1574^2 - 91 * 165^2 = 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2
1 0 -991
0 form 1 0 -991 delta 0
1 form -991 0 1 delta 31
2 form 1 62 -30
-1 -31
0 -1
To Return
-1 31
0 -1
0 form 1 62 -30 delta -2
1 form -30 58 5 delta 12
2 form 5 62 -6 delta -10
3 form -6 58 25 delta 2
4 form 25 42 -22 delta -2
5 form -22 46 21 delta 2
6 form 21 38 -30 delta -1
7 form -30 22 29 delta 1
8 form 29 36 -23 delta -2
9 form -23 56 9 delta 6
10 form 9 52 -35 delta -1
11 form -35 18 26 delta 1
12 form 26 34 -27 delta -1
13 form -27 20 33 delta 1
14 form 33 46 -14 delta -3
15 form -14 38 45 delta 1
16 form 45 52 -7 delta -8
17 form -7 60 13 delta 4
18 form 13 44 -39 delta -1
19 form -39 34 18 delta 2
20 form 18 38 -35 delta -1
21 form -35 32 21 delta 2
22 form 21 52 -15 delta -3
23 form -15 38 42 delta 1
24 form 42 46 -11 delta -4
25 form -11 42 50 delta 1
26 form 50 58 -3 delta -20
27 form -3 62 10 delta 6
28 form 10 58 -15 delta -4
29 form -15 62 2 delta 31
30 form 2 62 -15 delta -4
31 form -15 58 10 delta 6
32 form 10 62 -3 delta -20
33 form -3 58 50 delta 1
34 form 50 42 -11 delta -4
35 form -11 46 42 delta 1
36 form 42 38 -15 delta -3
37 form -15 52 21 delta 2
38 form 21 32 -35 delta -1
39 form -35 38 18 delta 2
40 form 18 34 -39 delta -1
41 form -39 44 13 delta 4
42 form 13 60 -7 delta -8
43 form -7 52 45 delta 1
44 form 45 38 -14 delta -3
45 form -14 46 33 delta 1
46 form 33 20 -27 delta -1
47 form -27 34 26 delta 1
48 form 26 18 -35 delta -1
49 form -35 52 9 delta 6
50 form 9 56 -23 delta -2
51 form -23 36 29 delta 1
52 form 29 22 -30 delta -1
53 form -30 38 21 delta 2
54 form 21 46 -22 delta -2
55 form -22 42 25 delta 2
56 form 25 58 -6 delta -10
57 form -6 62 5 delta 12
58 form 5 58 -30 delta -2
59 form -30 62 1 delta 62
60 form 1 62 -30
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
Following the link, taking (379,12, which was calculated by brute force) as the fundamental solution, we can get the generic solution.
I'm trying to replace the brute force with human intelligence(!) using the followings: first , second and continued fraction of $\sqrt{991}$