How to solve the following Pell's equation?
$$x^{2} - 991y^{2} = 1 $$ where $(x, y)$ are naturals.
The answer is $$x = 379,516,400,906,811,930,638,014,896,080$$ $$y = 12,055,735,790,331,359,447,442,538,767$$
I can't think of any way apart from brute force. Please help.
Also, what is the general way of solving any Pell's equation?
I read the wiki article on it but couldn't get any general method to solve it.
On
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}$
On
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} $$
On
$$x^2 - 991y^2 = 1$$ -------(1)
Assuming $y \not= 0$ divide both sides of the equation by $y^2$
i.e. $$(x/y)^2 - 991 = (1/y)^2$$
i.e. $(x/y)^2 - (1/y)^2 = 991$
i.e. $(x/y - 1/y)(x/y + 1/y) = (1)(991)$
i.e. $(x/y - 1/y)(x/y + 1/y) = (496 - 495)(496 + 495)$
i.e. $x/y = 496$ and $1/y = 495$
i.e. $x = (496/495)$ and $y = 1/495$
The equation represents a hyperbola of the form $$x^2/a^2 - y^2/b^2 = 1$$
i.e. the equation is $$x^2/(1^2) - y^2/(\sqrt {1/991})^2 = 1$$
foci of this hyperbola are the co ordinates $(\pm c, 0)$
Here $c = \sqrt{a^2 + b^2}$
The asymptotes are $y = \pm (b/a)x$
i.e. The asymptotes are $y = \pm (1/\sqrt{991})x$
There exists a $CONJUGATE$ $HYPERBOLA$ of the form $\frac{x^2}{a^2} - \frac{y^2}{b^2} = -1$, for the $HYPERBOLA$ $\frac{x^2}{a^2} - \frac{y^2}{b^2} = 1$
Here the equation of the $conjugate$ $hyperbola$ is $x^2 - 991(y^2) = -1$
$$x^2 - 991y^2 = -1$$ -------(2)
Now solve equations (1) and (2) for $x$ and $y$
i.e. $(2)(x^2) - (2)(991)(y^2) = 0$
i.e. $(x^2) - (991)(y^2) = 0$
i.e. $(x^2) = (991)(y^2)$
i.e. $\frac{x^2}{y^2} = 991$
i.e. $\left(\frac{x^2}{y^2} - (\sqrt{991})^2\right) = 0$
i.e. $\left(\frac{x}{y} - \sqrt{991}\right)\left(\frac{x}{y} + \sqrt{991}\right) = 0$
i.e. $(\frac{x}{y} = \pm\sqrt{991})$
i.e. $\frac{y}{x} = \pm\frac{1}{\sqrt{991}}$ , the equations of the asymptotes to the hyperbola
On
Here are the steps to find the solutions for all d = m^2 + 2k. In your question d = 991 which belongs to this category. The following five steps give the first solution and the fundamental solutions.
1) 991 = m^2 + 2k
991 - 31^2 = 2k
So m=31, k=15.
2) We set x = m^2 - m + k = 945
y = m - 1 = 30
945^2 - 991*30^2 = 1125 -> 189 - 991*6^2 = 45 -> 63^2 - 991*2^2 = 5
3) Now we will find the solvent as follows:
x_1 = m^2 + m + 2k = 1022
y_1 = m + 1 = 32
1022^2 - 991*32^2 = 29700 -> 511^2 - 991*16^2 = 7425
x_2 = m^2 - m + 2k = 960
y_2 = m - 1 = 30
960^2 - 991*30^2 = 29700 -> 480^2 - 991*15^2 =7425
From the following multiplication we find the value of the solvent:
(511 + 16*sqrt991)(480 + 15*sqrt991) -> 483120^2 - 991*15345^2 = 7425^2
4) We multiply the solvent by any of the first fundamental solutions to find the second fundamental solution:
(483120 + 15345*sqrt991)(945 + 30*sqrt991) -> 24586^2 - 991*781^2 = 45
5) From the multiplication (24586 + 781*sqrt991)(945 + 30*sqrt991) we obtain the third fundamental solution.
We can continue this process indefinitely to find more and more fundamental solutions.
On
had forgotten this one. I've got better programs now, including one that does Pell....
jagy@phobeusjunior:~/Desktop/Cplusplus$ ./Pell 991
Sun Jul 17 12:56:55 PDT 2022
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
=========================================
2
616049024759241^2 - 991 * 19569442212887^2 = 2
=========================================
2 Automorph, written on right of Gram matrix:
-9396316159744 -293541633193305
-19569442212887 -611350866679369
991 991
Sun Jul 17 12:56:55 PDT 2022
one I learned from Lubin
$$ \sqrt { 991} = 31 + \frac{ \sqrt {991} - 31 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{30 } = 2 + \frac{ \sqrt {991} - 29 }{30 } $$ $$ \frac{ 30 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{5 } = 12 + \frac{ \sqrt {991} - 31 }{5 } $$ $$ \frac{ 5 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{6 } = 10 + \frac{ \sqrt {991} - 29 }{6 } $$ $$ \frac{ 6 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{25 } = 2 + \frac{ \sqrt {991} - 21 }{25 } $$ $$ \frac{ 25 }{ \sqrt {991} - 21 } = \frac{ \sqrt {991} + 21 }{22 } = 2 + \frac{ \sqrt {991} - 23 }{22 } $$ $$ \frac{ 22 }{ \sqrt {991} - 23 } = \frac{ \sqrt {991} + 23 }{21 } = 2 + \frac{ \sqrt {991} - 19 }{21 } $$ $$ \frac{ 21 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{30 } = 1 + \frac{ \sqrt {991} - 11 }{30 } $$ $$ \frac{ 30 }{ \sqrt {991} - 11 } = \frac{ \sqrt {991} + 11 }{29 } = 1 + \frac{ \sqrt {991} - 18 }{29 } $$ $$ \frac{ 29 }{ \sqrt {991} - 18 } = \frac{ \sqrt {991} + 18 }{23 } = 2 + \frac{ \sqrt {991} - 28 }{23 } $$ $$ \frac{ 23 }{ \sqrt {991} - 28 } = \frac{ \sqrt {991} + 28 }{9 } = 6 + \frac{ \sqrt {991} - 26 }{9 } $$ $$ \frac{ 9 }{ \sqrt {991} - 26 } = \frac{ \sqrt {991} + 26 }{35 } = 1 + \frac{ \sqrt {991} - 9 }{35 } $$ $$ \frac{ 35 }{ \sqrt {991} - 9 } = \frac{ \sqrt {991} + 9 }{26 } = 1 + \frac{ \sqrt {991} - 17 }{26 } $$ $$ \frac{ 26 }{ \sqrt {991} - 17 } = \frac{ \sqrt {991} + 17 }{27 } = 1 + \frac{ \sqrt {991} - 10 }{27 } $$ $$ \frac{ 27 }{ \sqrt {991} - 10 } = \frac{ \sqrt {991} + 10 }{33 } = 1 + \frac{ \sqrt {991} - 23 }{33 } $$ $$ \frac{ 33 }{ \sqrt {991} - 23 } = \frac{ \sqrt {991} + 23 }{14 } = 3 + \frac{ \sqrt {991} - 19 }{14 } $$ $$ \frac{ 14 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{45 } = 1 + \frac{ \sqrt {991} - 26 }{45 } $$ $$ \frac{ 45 }{ \sqrt {991} - 26 } = \frac{ \sqrt {991} + 26 }{7 } = 8 + \frac{ \sqrt {991} - 30 }{7 } $$ $$ \frac{ 7 }{ \sqrt {991} - 30 } = \frac{ \sqrt {991} + 30 }{13 } = 4 + \frac{ \sqrt {991} - 22 }{13 } $$ $$ \frac{ 13 }{ \sqrt {991} - 22 } = \frac{ \sqrt {991} + 22 }{39 } = 1 + \frac{ \sqrt {991} - 17 }{39 } $$ $$ \frac{ 39 }{ \sqrt {991} - 17 } = \frac{ \sqrt {991} + 17 }{18 } = 2 + \frac{ \sqrt {991} - 19 }{18 } $$ $$ \frac{ 18 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{35 } = 1 + \frac{ \sqrt {991} - 16 }{35 } $$ $$ \frac{ 35 }{ \sqrt {991} - 16 } = \frac{ \sqrt {991} + 16 }{21 } = 2 + \frac{ \sqrt {991} - 26 }{21 } $$ $$ \frac{ 21 }{ \sqrt {991} - 26 } = \frac{ \sqrt {991} + 26 }{15 } = 3 + \frac{ \sqrt {991} - 19 }{15 } $$ $$ \frac{ 15 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{42 } = 1 + \frac{ \sqrt {991} - 23 }{42 } $$ $$ \frac{ 42 }{ \sqrt {991} - 23 } = \frac{ \sqrt {991} + 23 }{11 } = 4 + \frac{ \sqrt {991} - 21 }{11 } $$ $$ \frac{ 11 }{ \sqrt {991} - 21 } = \frac{ \sqrt {991} + 21 }{50 } = 1 + \frac{ \sqrt {991} - 29 }{50 } $$ $$ \frac{ 50 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{3 } = 20 + \frac{ \sqrt {991} - 31 }{3 } $$ $$ \frac{ 3 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{10 } = 6 + \frac{ \sqrt {991} - 29 }{10 } $$ $$ \frac{ 10 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{15 } = 4 + \frac{ \sqrt {991} - 31 }{15 } $$ $$ \frac{ 15 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{2 } = 31 + \frac{ \sqrt {991} - 31 }{2 } $$ $$ \frac{ 2 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{15 } = 4 + \frac{ \sqrt {991} - 29 }{15 } $$ $$ \frac{ 15 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{10 } = 6 + \frac{ \sqrt {991} - 31 }{10 } $$ $$ \frac{ 10 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{3 } = 20 + \frac{ \sqrt {991} - 29 }{3 } $$ $$ \frac{ 3 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{50 } = 1 + \frac{ \sqrt {991} - 21 }{50 } $$ $$ \frac{ 50 }{ \sqrt {991} - 21 } = \frac{ \sqrt {991} + 21 }{11 } = 4 + \frac{ \sqrt {991} - 23 }{11 } $$ $$ \frac{ 11 }{ \sqrt {991} - 23 } = \frac{ \sqrt {991} + 23 }{42 } = 1 + \frac{ \sqrt {991} - 19 }{42 } $$ $$ \frac{ 42 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{15 } = 3 + \frac{ \sqrt {991} - 26 }{15 } $$ $$ \frac{ 15 }{ \sqrt {991} - 26 } = \frac{ \sqrt {991} + 26 }{21 } = 2 + \frac{ \sqrt {991} - 16 }{21 } $$ $$ \frac{ 21 }{ \sqrt {991} - 16 } = \frac{ \sqrt {991} + 16 }{35 } = 1 + \frac{ \sqrt {991} - 19 }{35 } $$ $$ \frac{ 35 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{18 } = 2 + \frac{ \sqrt {991} - 17 }{18 } $$ $$ \frac{ 18 }{ \sqrt {991} - 17 } = \frac{ \sqrt {991} + 17 }{39 } = 1 + \frac{ \sqrt {991} - 22 }{39 } $$ $$ \frac{ 39 }{ \sqrt {991} - 22 } = \frac{ \sqrt {991} + 22 }{13 } = 4 + \frac{ \sqrt {991} - 30 }{13 } $$ $$ \frac{ 13 }{ \sqrt {991} - 30 } = \frac{ \sqrt {991} + 30 }{7 } = 8 + \frac{ \sqrt {991} - 26 }{7 } $$ $$ \frac{ 7 }{ \sqrt {991} - 26 } = \frac{ \sqrt {991} + 26 }{45 } = 1 + \frac{ \sqrt {991} - 19 }{45 } $$ $$ \frac{ 45 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{14 } = 3 + \frac{ \sqrt {991} - 23 }{14 } $$ $$ \frac{ 14 }{ \sqrt {991} - 23 } = \frac{ \sqrt {991} + 23 }{33 } = 1 + \frac{ \sqrt {991} - 10 }{33 } $$ $$ \frac{ 33 }{ \sqrt {991} - 10 } = \frac{ \sqrt {991} + 10 }{27 } = 1 + \frac{ \sqrt {991} - 17 }{27 } $$ $$ \frac{ 27 }{ \sqrt {991} - 17 } = \frac{ \sqrt {991} + 17 }{26 } = 1 + \frac{ \sqrt {991} - 9 }{26 } $$ $$ \frac{ 26 }{ \sqrt {991} - 9 } = \frac{ \sqrt {991} + 9 }{35 } = 1 + \frac{ \sqrt {991} - 26 }{35 } $$ $$ \frac{ 35 }{ \sqrt {991} - 26 } = \frac{ \sqrt {991} + 26 }{9 } = 6 + \frac{ \sqrt {991} - 28 }{9 } $$ $$ \frac{ 9 }{ \sqrt {991} - 28 } = \frac{ \sqrt {991} + 28 }{23 } = 2 + \frac{ \sqrt {991} - 18 }{23 } $$ $$ \frac{ 23 }{ \sqrt {991} - 18 } = \frac{ \sqrt {991} + 18 }{29 } = 1 + \frac{ \sqrt {991} - 11 }{29 } $$ $$ \frac{ 29 }{ \sqrt {991} - 11 } = \frac{ \sqrt {991} + 11 }{30 } = 1 + \frac{ \sqrt {991} - 19 }{30 } $$ $$ \frac{ 30 }{ \sqrt {991} - 19 } = \frac{ \sqrt {991} + 19 }{21 } = 2 + \frac{ \sqrt {991} - 23 }{21 } $$ $$ \frac{ 21 }{ \sqrt {991} - 23 } = \frac{ \sqrt {991} + 23 }{22 } = 2 + \frac{ \sqrt {991} - 21 }{22 } $$ $$ \frac{ 22 }{ \sqrt {991} - 21 } = \frac{ \sqrt {991} + 21 }{25 } = 2 + \frac{ \sqrt {991} - 29 }{25 } $$ $$ \frac{ 25 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{6 } = 10 + \frac{ \sqrt {991} - 31 }{6 } $$ $$ \frac{ 6 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{5 } = 12 + \frac{ \sqrt {991} - 29 }{5 } $$ $$ \frac{ 5 }{ \sqrt {991} - 29 } = \frac{ \sqrt {991} + 29 }{30 } = 2 + \frac{ \sqrt {991} - 31 }{30 } $$ $$ \frac{ 30 }{ \sqrt {991} - 31 } = \frac{ \sqrt {991} + 31 }{1 } = 62 + \frac{ \sqrt {991} - 31 }{1 } $$
Simple continued fraction tableau:
$$
\begin{array}{cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc}
& & 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 & \\
\\
\frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 31 }{ 1 } & & \frac{ 63 }{ 2 } & & \frac{ 787 }{ 25 } & & \frac{ 7933 }{ 252 } & & \frac{ 16653 }{ 529 } & & \frac{ 41239 }{ 1310 } & & \frac{ 99131 }{ 3149 } & & \frac{ 140370 }{ 4459 } & & \frac{ 239501 }{ 7608 } & & \frac{ 619372 }{ 19675 } & & \frac{ 3955733 }{ 125658 } & & \frac{ 4575105 }{ 145333 } & & \frac{ 8530838 }{ 270991 } & & \frac{ 13105943 }{ 416324 } & & \frac{ 21636781 }{ 687315 } & & \frac{ 78016286 }{ 2478269 } & & \frac{ 99653067 }{ 3165584 } & & \frac{ 875240822 }{ 27802941 } & & \frac{ 3600616355 }{ 114377348 } & & \frac{ 4475857177 }{ 142180289 } & & \frac{ 12552330709 }{ 398737926 } & & \frac{ 17028187886 }{ 540918215 } & & \frac{ 46608706481 }{ 1480574356 } & & \frac{ 156854307329 }{ 4982641283 } & & \frac{ 203463013810 }{ 6463215639 } & & \frac{ 970706362569 }{ 30835503839 } & & \frac{ 1174169376379 }{ 37298719478 } & & \frac{ 24454093890149 }{ 776809893399 } & & \frac{ 147898732717273 }{ 4698158079872 } & & \frac{ 616049024759241 }{ 19569442212887 } & & \frac{ 19245418500253744 }{ 611350866679369 } & & \frac{ 77597723025774217 }{ 2464972908930363 } & & \frac{ 484831756654899046 }{ 15401188320261547 } & & \frac{ 9774232856123755137 }{ 310488739314161303 } & & \frac{ 10259064612778654183 }{ 325889927634422850 } & & \frac{ 50810491307238371869 }{ 1614048449851852703 } & & \frac{ 61069555920017026052 }{ 1939938377486275553 } & & \frac{ 234019159067289450025 }{ 7433863582310679362 } & & \frac{ 529107874054595926102 }{ 16807665542107634277 } & & \frac{ 763127033121885376127 }{ 24241529124418313639 } & & \frac{ 2055361940298366678356 }{ 65290723790944261555 } & & \frac{ 2818488973420252054483 }{ 89532252915362575194 } & & \frac{ 13329317833979374896288 }{ 423419735452394562331 } & & \frac{ 109453031645255251224787 }{ 3476890136534519073842 } & & \frac{ 122782349479234626121075 }{ 3900309871986913636173 } & & \frac{ 477800080082959129588012 }{ 15177819752495259982361 } & & \frac{ 600582429562193755709087 }{ 19078129624482173618534 } & & \frac{ 1078382509645152885297099 }{ 34255949376977433600895 } & & \frac{ 1678964939207346641006186 }{ 53334079001459607219429 } & & \frac{ 2757347448852499526303285 }{ 87590028378437040820324 } & & \frac{ 18223049632322343798825896 }{ 578874249272081852141373 } & & \frac{ 39203446713497187123955077 }{ 1245338526922600745103070 } & & \frac{ 57426496345819530922780973 }{ 1824212776194682597244443 } & & \frac{ 96629943059316718046736050 }{ 3069551303117283342347513 } & & \frac{ 250686382464452967016253073 }{ 7963315382429249281939469 } & & \frac{ 598002707988222652079242196 }{ 18996182067975781906226451 } & & \frac{ 1446691798440898271174737465 }{ 45955679518380813094392371 } & & \frac{ 15064920692397205363826616846 }{ 478552977251783912850150161 } & & \frac{ 182225740107207362637094139617 }{ 5788591406539787767296194303 } & & \frac{ 379516400906811930638014896080 }{ 12055735790331359447442538767 } \\
\\
& 1 & & -30 & & 5 & & -6 & & 25 & & -22 & & 21 & & -30 & & 29 & & -23 & & 9 & & -35 & & 26 & & -27 & & 33 & & -14 & & 45 & & -7 & & 13 & & -39 & & 18 & & -35 & & 21 & & -15 & & 42 & & -11 & & 50 & & -3 & & 10 & & -15 & & 2 & & -15 & & 10 & & -3 & & 50 & & -11 & & 42 & & -15 & & 21 & & -35 & & 18 & & -39 & & 13 & & -7 & & 45 & & -14 & & 33 & & -27 & & 26 & & -35 & & 9 & & -23 & & 29 & & -30 & & 21 & & -22 & & 25 & & -6 & & 5 & & -30 & & 1
\end{array}
$$
$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 991 \cdot 0^2 = 1 & \mbox{digit} & 31 \\ \frac{ 31 }{ 1 } & 31^2 - 991 \cdot 1^2 = -30 & \mbox{digit} & 2 \\ \frac{ 63 }{ 2 } & 63^2 - 991 \cdot 2^2 = 5 & \mbox{digit} & 12 \\ \frac{ 787 }{ 25 } & 787^2 - 991 \cdot 25^2 = -6 & \mbox{digit} & 10 \\ \frac{ 7933 }{ 252 } & 7933^2 - 991 \cdot 252^2 = 25 & \mbox{digit} & 2 \\ \frac{ 16653 }{ 529 } & 16653^2 - 991 \cdot 529^2 = -22 & \mbox{digit} & 2 \\ \frac{ 41239 }{ 1310 } & 41239^2 - 991 \cdot 1310^2 = 21 & \mbox{digit} & 2 \\ \frac{ 99131 }{ 3149 } & 99131^2 - 991 \cdot 3149^2 = -30 & \mbox{digit} & 1 \\ \frac{ 140370 }{ 4459 } & 140370^2 - 991 \cdot 4459^2 = 29 & \mbox{digit} & 1 \\ \frac{ 239501 }{ 7608 } & 239501^2 - 991 \cdot 7608^2 = -23 & \mbox{digit} & 2 \\ \frac{ 619372 }{ 19675 } & 619372^2 - 991 \cdot 19675^2 = 9 & \mbox{digit} & 6 \\ \frac{ 3955733 }{ 125658 } & 3955733^2 - 991 \cdot 125658^2 = -35 & \mbox{digit} & 1 \\ \frac{ 4575105 }{ 145333 } & 4575105^2 - 991 \cdot 145333^2 = 26 & \mbox{digit} & 1 \\ \frac{ 8530838 }{ 270991 } & 8530838^2 - 991 \cdot 270991^2 = -27 & \mbox{digit} & 1 \\ \frac{ 13105943 }{ 416324 } & 13105943^2 - 991 \cdot 416324^2 = 33 & \mbox{digit} & 1 \\ \frac{ 21636781 }{ 687315 } & 21636781^2 - 991 \cdot 687315^2 = -14 & \mbox{digit} & 3 \\ \frac{ 78016286 }{ 2478269 } & 78016286^2 - 991 \cdot 2478269^2 = 45 & \mbox{digit} & 1 \\ \frac{ 99653067 }{ 3165584 } & 99653067^2 - 991 \cdot 3165584^2 = -7 & \mbox{digit} & 8 \\ \frac{ 875240822 }{ 27802941 } & 875240822^2 - 991 \cdot 27802941^2 = 13 & \mbox{digit} & 4 \\ \frac{ 3600616355 }{ 114377348 } & 3600616355^2 - 991 \cdot 114377348^2 = -39 & \mbox{digit} & 1 \\ \frac{ 4475857177 }{ 142180289 } & 4475857177^2 - 991 \cdot 142180289^2 = 18 & \mbox{digit} & 2 \\ \frac{ 12552330709 }{ 398737926 } & 12552330709^2 - 991 \cdot 398737926^2 = -35 & \mbox{digit} & 1 \\ \frac{ 17028187886 }{ 540918215 } & 17028187886^2 - 991 \cdot 540918215^2 = 21 & \mbox{digit} & 2 \\ \frac{ 46608706481 }{ 1480574356 } & 46608706481^2 - 991 \cdot 1480574356^2 = -15 & \mbox{digit} & 3 \\ \frac{ 156854307329 }{ 4982641283 } & 156854307329^2 - 991 \cdot 4982641283^2 = 42 & \mbox{digit} & 1 \\ \frac{ 203463013810 }{ 6463215639 } & 203463013810^2 - 991 \cdot 6463215639^2 = -11 & \mbox{digit} & 4 \\ \frac{ 970706362569 }{ 30835503839 } & 970706362569^2 - 991 \cdot 30835503839^2 = 50 & \mbox{digit} & 1 \\ \frac{ 1174169376379 }{ 37298719478 } & 1174169376379^2 - 991 \cdot 37298719478^2 = -3 & \mbox{digit} & 20 \\ \frac{ 24454093890149 }{ 776809893399 } & 24454093890149^2 - 991 \cdot 776809893399^2 = 10 & \mbox{digit} & 6 \\ \frac{ 147898732717273 }{ 4698158079872 } & 147898732717273^2 - 991 \cdot 4698158079872^2 = -15 & \mbox{digit} & 4 \\ \frac{ 616049024759241 }{ 19569442212887 } & 616049024759241^2 - 991 \cdot 19569442212887^2 = 2 & \mbox{digit} & 31 \\ \frac{ 19245418500253744 }{ 611350866679369 } & 19245418500253744^2 - 991 \cdot 611350866679369^2 = -15 & \mbox{digit} & 4 \\ \frac{ 77597723025774217 }{ 2464972908930363 } & 77597723025774217^2 - 991 \cdot 2464972908930363^2 = 10 & \mbox{digit} & 6 \\ \frac{ 484831756654899046 }{ 15401188320261547 } & 484831756654899046^2 - 991 \cdot 15401188320261547^2 = -3 & \mbox{digit} & 20 \\ \frac{ 9774232856123755137 }{ 310488739314161303 } & 9774232856123755137^2 - 991 \cdot 310488739314161303^2 = 50 & \mbox{digit} & 1 \\ \frac{ 10259064612778654183 }{ 325889927634422850 } & 10259064612778654183^2 - 991 \cdot 325889927634422850^2 = -11 & \mbox{digit} & 4 \\ \frac{ 50810491307238371869 }{ 1614048449851852703 } & 50810491307238371869^2 - 991 \cdot 1614048449851852703^2 = 42 & \mbox{digit} & 1 \\ \frac{ 61069555920017026052 }{ 1939938377486275553 } & 61069555920017026052^2 - 991 \cdot 1939938377486275553^2 = -15 & \mbox{digit} & 3 \\ \frac{ 234019159067289450025 }{ 7433863582310679362 } & 234019159067289450025^2 - 991 \cdot 7433863582310679362^2 = 21 & \mbox{digit} & 2 \\ \frac{ 529107874054595926102 }{ 16807665542107634277 } & 529107874054595926102^2 - 991 \cdot 16807665542107634277^2 = -35 & \mbox{digit} & 1 \\ \frac{ 763127033121885376127 }{ 24241529124418313639 } & 763127033121885376127^2 - 991 \cdot 24241529124418313639^2 = 18 & \mbox{digit} & 2 \\ \frac{ 2055361940298366678356 }{ 65290723790944261555 } & 2055361940298366678356^2 - 991 \cdot 65290723790944261555^2 = -39 & \mbox{digit} & 1 \\ \frac{ 2818488973420252054483 }{ 89532252915362575194 } & 2818488973420252054483^2 - 991 \cdot 89532252915362575194^2 = 13 & \mbox{digit} & 4 \\ \frac{ 13329317833979374896288 }{ 423419735452394562331 } & 13329317833979374896288^2 - 991 \cdot 423419735452394562331^2 = -7 & \mbox{digit} & 8 \\ \frac{ 109453031645255251224787 }{ 3476890136534519073842 } & 109453031645255251224787^2 - 991 \cdot 3476890136534519073842^2 = 45 & \mbox{digit} & 1 \\ \frac{ 122782349479234626121075 }{ 3900309871986913636173 } & 122782349479234626121075^2 - 991 \cdot 3900309871986913636173^2 = -14 & \mbox{digit} & 3 \\ \frac{ 477800080082959129588012 }{ 15177819752495259982361 } & 477800080082959129588012^2 - 991 \cdot 15177819752495259982361^2 = 33 & \mbox{digit} & 1 \\ \frac{ 600582429562193755709087 }{ 19078129624482173618534 } & 600582429562193755709087^2 - 991 \cdot 19078129624482173618534^2 = -27 & \mbox{digit} & 1 \\ \frac{ 1078382509645152885297099 }{ 34255949376977433600895 } & 1078382509645152885297099^2 - 991 \cdot 34255949376977433600895^2 = 26 & \mbox{digit} & 1 \\ \frac{ 1678964939207346641006186 }{ 53334079001459607219429 } & 1678964939207346641006186^2 - 991 \cdot 53334079001459607219429^2 = -35 & \mbox{digit} & 1 \\ \frac{ 2757347448852499526303285 }{ 87590028378437040820324 } & 2757347448852499526303285^2 - 991 \cdot 87590028378437040820324^2 = 9 & \mbox{digit} & 6 \\ \frac{ 18223049632322343798825896 }{ 578874249272081852141373 } & 18223049632322343798825896^2 - 991 \cdot 578874249272081852141373^2 = -23 & \mbox{digit} & 2 \\ \frac{ 39203446713497187123955077 }{ 1245338526922600745103070 } & 39203446713497187123955077^2 - 991 \cdot 1245338526922600745103070^2 = 29 & \mbox{digit} & 1 \\ \frac{ 57426496345819530922780973 }{ 1824212776194682597244443 } & 57426496345819530922780973^2 - 991 \cdot 1824212776194682597244443^2 = -30 & \mbox{digit} & 1 \\ \frac{ 96629943059316718046736050 }{ 3069551303117283342347513 } & 96629943059316718046736050^2 - 991 \cdot 3069551303117283342347513^2 = 21 & \mbox{digit} & 2 \\ \frac{ 250686382464452967016253073 }{ 7963315382429249281939469 } & 250686382464452967016253073^2 - 991 \cdot 7963315382429249281939469^2 = -22 & \mbox{digit} & 2 \\ \frac{ 598002707988222652079242196 }{ 18996182067975781906226451 } & 598002707988222652079242196^2 - 991 \cdot 18996182067975781906226451^2 = 25 & \mbox{digit} & 2 \\ \frac{ 1446691798440898271174737465 }{ 45955679518380813094392371 } & 1446691798440898271174737465^2 - 991 \cdot 45955679518380813094392371^2 = -6 & \mbox{digit} & 10 \\ \frac{ 15064920692397205363826616846 }{ 478552977251783912850150161 } & 15064920692397205363826616846^2 - 991 \cdot 478552977251783912850150161^2 = 5 & \mbox{digit} & 12 \\ \frac{ 182225740107207362637094139617 }{ 5788591406539787767296194303 } & 182225740107207362637094139617^2 - 991 \cdot 5788591406539787767296194303^2 = -30 & \mbox{digit} & 2 \\ \frac{ 379516400906811930638014896080 }{ 12055735790331359447442538767 } & 379516400906811930638014896080^2 - 991 \cdot 12055735790331359447442538767^2 = 1 & \mbox{digit} & 62 \\ \end{array} $$
379516400906811930638014896080 mod 991 = 1
-39, -35, -30, -27, -23, -22, -15, -14, -11, -7,
-6, -3, 1, 2, 5, 9, 10, 13, 18, 21,
25, 26, 29, 33, 42, 45, 50,
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.
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:
Let me start with an easier one, 91, where I do get an answer, then show 991 after: