# How to solve this Pell's equation $x^{2} - 991y^{2} = 1$

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$$

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.

• Read this. – Eugene Jul 17 '12 at 3:49
• Here's a useful online solver, select "step-by-step" to see the methods used. – Bill Dubuque Jul 17 '12 at 4:23
• x3/y3=218651085477388313475594044993514033413718343388164019627976764578114609092763357330159760/6945680635899069348063079893854789105557565351617874814495165631493551941446359906376433 – user325858 Mar 25 '16 at 14:48

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$ 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} 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}$• Isn't the fundamental solution actually a solution? I get$379^2-991\cdot12^2=937$. – robjohn Jul 18 '12 at 17:21 • It is. While focusing the procedure, I actually missed to observe that none of the pairs supplied in the question satisfies the equation. Programmatically, I observer that (775587755, 24637357) is probably the minimum solution after the trivial pairs(±1,0). Next pair being (875240822, 27802941) – lab bhattacharjee Jul 19 '12 at 6:18 • The "pairs supplied in the question" were not pairs, but a couple of large numbers written with comma separators. Those are the same numbers given in$(4)$in my answer. Those numbers are the smallest positive solution (all solutions are given in$(6)$). – robjohn Jul 19 '12 at 9:35 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. I think it can be solved without using complex operators,and the solution is here: When is$991n^2 +1$a perfect square? All you really have to do is brute force the smallest pair (x, y) and the rest is cake. Once you find it, throw it into a 2×2 matrix with both diagonal entries that are the x coordinate and the Anti-diagonal entries being y and y*991 (doesnt matter). The determinant of this guy is 1. Diagonalize the matrix, take to a power s, where s is n integer, and then multiply it back out. The determinant is still one. Thats how you get all other solutions. $$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$CONJUGATEHYPERBOLA$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$conjugatehyperbola$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 • Try putting$\$ s at the start and end of your mathematics – preferred_anon Jul 19 '12 at 16:04

Solving method from Pell’s equation without irrational numbers by Norman Wildberger

in pari/gp:

njw(d)=
{
L= [1,0;1,1]; R= [1,1;0,1];
A= [1,0;0,-d]; Q= A; N= 1;
while(1,
a= Q[1,1]; b= Q[1,2]; c= Q[2,2];
t= a+2*b+c;
if(t<0, Q= R~*Q*R; N= N*R, Q= L~*Q*L; N= N*L);
if(Q==A, break())
);
return(N[,1]~)
};

? njw(991)
%5 = [379516400906811930638014896080, 12055735790331359447442538767]


Also this method online in Geogebra