# How to find a fundamental solution to Pell's equation?

It is quite straightforward to find the fundamental solutions for a given Pell's equation when $d$ is small. But I am unable to solve this equation, as I'm unable to find the fundamental solutions:

Solve: $x^2-29y^2=1$ and $x^2-29y^2=-1$ with $y\not=0$.

Could you please guide me through the solution

• The first integer solution with $|x|>1$ is $x=\pm9801$. – Lucian Dec 1 '14 at 5:37
• The fundamental solution to x^2−29y^2=1 is (9801, 1820) according to had2know.com/academics/pell-equation-calculator.html. But I want to know the method to calculate this. – L887 Dec 1 '14 at 7:02
• A commonly used method to find the fundamental solution to the Pell's equation is the Dirichlet's approximation theorem, but I didn't understand how to apply it. Could anyone throw some light on this.Thanks – L887 Dec 1 '14 at 7:32
• @WillJagy Yes you are right, we can use the method discovered by Gauss and Lagrange, but in order to do so you need to first find out the fundamental solutions and then you could use the recursive formulae formulated by them to find the rest of the solutions trivially.These formulae were derived by them using the Pigeon hole principle. But as you see although 29 seems like a small number the fundamental solution is very large. So how do we go about it in such cases using only mechanical calculation techniques? – L887 Dec 1 '14 at 7:38
• L887, I meant something rather different, equivalent to continued fractions, which you should learn in any case, continued fractions are quite easy. – Will Jagy Dec 1 '14 at 20:36

The standard method for finding the fundamental solution is continued fractions for $\sqrt {29},$ and would not be difficult with a calculator. HERE is a summary using $\sqrt 7$ instead. Gauss and Lagrange made an equivalent but better method with "reduced" quadratic forms, that requires no decimal accuracy for the square root, just the integer part, just integer arithmetic, and no "cycle detection." I have described it often on this site. http://math.blogoverflow.com/2014/08/23/binary-quadratic-forms-over-the-rational-integers-and-class-numbers-of-quadratic-%EF%AC%81elds/

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./Pell 29 0 form 1 10 -4 delta -2 1 form -4 6 5 delta 1 2 form 5 4 -5 delta -1 3 form -5 6 4 delta 2 4 form 4 10 -1 delta -10 5 form -1 10 4 delta 2 6 form 4 6 -5 delta -1 7 form -5 4 5 delta 1 8 form 5 6 -4 delta -2 9 form -4 10 1 delta 10 10 form 1 10 -4 Pell automorph 9801 52780 1820 9801 Pell unit 9801^2 - 29 * 1820^2 = 1 ========================================= Pell NEGATIVE 70^2 - 29 * 13^2 = -1 ========================================= 4 PRIMITIVE 27^2 - 29 * 5^2 = 4 ========================================= -4 PRIMITIVE 3775^2 - 29 * 701^2 = -4 NOTE by hand: 5^2 - 29 * 1^2 = -4 was passed over by my program; that's life. =========================================  Well. The general, reliable method is continued fractions. Doing these with an ordinary calculator for$\sqrt n$will work nicely for most small$n.$However, as you can check in various places, this becomes problematic for$\sqrt {61}.$You can switch to continued fractions with large decimal accuracy on computer, but eventually one runs into problems. The method above is very similar to continued fractions, it just has a more careful style of bookkeeping, with the result that it always works. The fundamental theorem here is due to Lagrange, I will put a jpeg from a 1929 book by L. E. Dickson, it is Theorem 85. Notice that everyone is now using LED light bulbs, that can't be a coincidence. • Thanks Will Jagy you are awesome ! :) – L887 Dec 4 '14 at 5:17 (Too long for a comment.) If you're lucky and your discriminant$d$has a certain form ($d = 5, 13, 21, 29, 53, 61, \dots$), you can use the smaller fundamental solutions of the Pell equation, $$p^2-dq^2 = -4\tag{1}$$ Let, $$\left(\frac{p+q\sqrt{d}}{2}\right)^3=u+v\sqrt{d}\tag2$$ $$\left(\frac{p+q\sqrt{d}}{2}\right)^6=x+y\sqrt{d}\tag3$$ then, $$u^2-dv^2 = -1\tag4$$ $$x^2-dy^2 = 1\tag5$$ If fundamental$p,q$are odd, then$(2),(3)$are also fundamental. For your$d=29$, it is just$p,q = 5,1$. Hence the fundamental unit, $$U_{29} =\tfrac{5+\sqrt{29}}{2}$$ and, $$\big(U_{29}\big)^3=70+13\sqrt{29},\quad \text{thus}\;\;\color{blue}{70}^2-29\cdot\color{blue}{13}^2=-1$$ $$\big(U_{29}\big)^6=9801+1820\sqrt{29},\quad \text{thus}\;\;\color{blue}{9801}^2-29\cdot1820^2=1$$ $$2^6\left(\big(U_{29}\big)^6+\big(U_{29}\big)^{-6}\right)^2 =\color{blue}{396^4}$$ Incidentally, since certain eta quotients involve$U_{29}$, we find those integers all over Ramanujan's famous pi formula, $$\frac{1}{\pi} = \frac{2 \sqrt 2}{\color{blue}{9801}} \sum_{k=0}^\infty \frac{(4k)!}{k!^4} \frac{29\cdot\color{blue}{70\cdot13}\,k+1103}{\color{blue}{(396^4)}^k}$$ Nice, eh? Method described by Prof. Lubin at Continued fraction of$\sqrt{67} - 4\$

$$\sqrt { 29} = 5 + \frac{ \sqrt {29} - 5 }{ 1 }$$ $$\frac{ 1 }{ \sqrt {29} - 5 } = \frac{ \sqrt {29} + 5 }{4 } = 2 + \frac{ \sqrt {29} - 3 }{4 }$$ $$\frac{ 4 }{ \sqrt {29} - 3 } = \frac{ \sqrt {29} + 3 }{5 } = 1 + \frac{ \sqrt {29} - 2 }{5 }$$ $$\frac{ 5 }{ \sqrt {29} - 2 } = \frac{ \sqrt {29} + 2 }{5 } = 1 + \frac{ \sqrt {29} - 3 }{5 }$$ $$\frac{ 5 }{ \sqrt {29} - 3 } = \frac{ \sqrt {29} + 3 }{4 } = 2 + \frac{ \sqrt {29} - 5 }{4 }$$ $$\frac{ 4 }{ \sqrt {29} - 5 } = \frac{ \sqrt {29} + 5 }{1 } = 10 + \frac{ \sqrt {29} - 5 }{1 }$$

Simple continued fraction tableau:
$$\begin{array}{cccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 5 }{ 1 } & & \frac{ 11 }{ 2 } & & \frac{ 16 }{ 3 } & & \frac{ 27 }{ 5 } & & \frac{ 70 }{ 13 } & & \frac{ 727 }{ 135 } & & \frac{ 1524 }{ 283 } & & \frac{ 2251 }{ 418 } & & \frac{ 3775 }{ 701 } & & \frac{ 9801 }{ 1820 } \\ \\ & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 \end{array}$$

$$\begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 29 \cdot 0^2 = 1 & \mbox{digit} & 5 \\ \frac{ 5 }{ 1 } & 5^2 - 29 \cdot 1^2 = -4 & \mbox{digit} & 2 \\ \frac{ 11 }{ 2 } & 11^2 - 29 \cdot 2^2 = 5 & \mbox{digit} & 1 \\ \frac{ 16 }{ 3 } & 16^2 - 29 \cdot 3^2 = -5 & \mbox{digit} & 1 \\ \frac{ 27 }{ 5 } & 27^2 - 29 \cdot 5^2 = 4 & \mbox{digit} & 2 \\ \frac{ 70 }{ 13 } & 70^2 - 29 \cdot 13^2 = -1 & \mbox{digit} & 10 \\ \frac{ 727 }{ 135 } & 727^2 - 29 \cdot 135^2 = 4 & \mbox{digit} & 2 \\ \frac{ 1524 }{ 283 } & 1524^2 - 29 \cdot 283^2 = -5 & \mbox{digit} & 1 \\ \frac{ 2251 }{ 418 } & 2251^2 - 29 \cdot 418^2 = 5 & \mbox{digit} & 1 \\ \frac{ 3775 }{ 701 } & 3775^2 - 29 \cdot 701^2 = -4 & \mbox{digit} & 2 \\ \frac{ 9801 }{ 1820 } & 9801^2 - 29 \cdot 1820^2 = 1 & \mbox{digit} & 10 \\ \end{array}$$

======================================================================================

$$\sqrt { 95} = 9 + \frac{ \sqrt {95} - 9 }{ 1 }$$ $$\frac{ 1 }{ \sqrt {95} - 9 } = \frac{ \sqrt {95} + 9 }{14 } = 1 + \frac{ \sqrt {95} - 5 }{14 }$$ $$\frac{ 14 }{ \sqrt {95} - 5 } = \frac{ \sqrt {95} + 5 }{5 } = 2 + \frac{ \sqrt {95} - 5 }{5 }$$ $$\frac{ 5 }{ \sqrt {95} - 5 } = \frac{ \sqrt {95} + 5 }{14 } = 1 + \frac{ \sqrt {95} - 9 }{14 }$$ $$\frac{ 14 }{ \sqrt {95} - 9 } = \frac{ \sqrt {95} + 9 }{1 } = 18 + \frac{ \sqrt {95} - 9 }{1 }$$

Simple continued fraction tableau:
$$\begin{array}{cccccccccccccc} & & 9 & & 1 & & 2 & & 1 & & 18 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 9 }{ 1 } & & \frac{ 10 }{ 1 } & & \frac{ 29 }{ 3 } & & \frac{ 39 }{ 4 } \\ \\ & 1 & & -14 & & 5 & & -14 & & 1 \end{array}$$

$$\begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 95 \cdot 0^2 = 1 & \mbox{digit} & 9 \\ \frac{ 9 }{ 1 } & 9^2 - 95 \cdot 1^2 = -14 & \mbox{digit} & 1 \\ \frac{ 10 }{ 1 } & 10^2 - 95 \cdot 1^2 = 5 & \mbox{digit} & 2 \\ \frac{ 29 }{ 3 } & 29^2 - 95 \cdot 3^2 = -14 & \mbox{digit} & 1 \\ \frac{ 39 }{ 4 } & 39^2 - 95 \cdot 4^2 = 1 & \mbox{digit} & 18 \\ \end{array}$$

=================================================================================

$$\sqrt { 74} = 8 + \frac{ \sqrt {74} - 8 }{ 1 }$$ $$\frac{ 1 }{ \sqrt {74} - 8 } = \frac{ \sqrt {74} + 8 }{10 } = 1 + \frac{ \sqrt {74} - 2 }{10 }$$ $$\frac{ 10 }{ \sqrt {74} - 2 } = \frac{ \sqrt {74} + 2 }{7 } = 1 + \frac{ \sqrt {74} - 5 }{7 }$$ $$\frac{ 7 }{ \sqrt {74} - 5 } = \frac{ \sqrt {74} + 5 }{7 } = 1 + \frac{ \sqrt {74} - 2 }{7 }$$ $$\frac{ 7 }{ \sqrt {74} - 2 } = \frac{ \sqrt {74} + 2 }{10 } = 1 + \frac{ \sqrt {74} - 8 }{10 }$$ $$\frac{ 10 }{ \sqrt {74} - 8 } = \frac{ \sqrt {74} + 8 }{1 } = 16 + \frac{ \sqrt {74} - 8 }{1 }$$

Simple continued fraction tableau:
$$\begin{array}{cccccccccccccccccccccccc} & & 8 & & 1 & & 1 & & 1 & & 1 & & 16 & & 1 & & 1 & & 1 & & 1 & & 16 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 8 }{ 1 } & & \frac{ 9 }{ 1 } & & \frac{ 17 }{ 2 } & & \frac{ 26 }{ 3 } & & \frac{ 43 }{ 5 } & & \frac{ 714 }{ 83 } & & \frac{ 757 }{ 88 } & & \frac{ 1471 }{ 171 } & & \frac{ 2228 }{ 259 } & & \frac{ 3699 }{ 430 } \\ \\ & 1 & & -10 & & 7 & & -7 & & 10 & & -1 & & 10 & & -7 & & 7 & & -10 & & 1 \end{array}$$

$$\begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 74 \cdot 0^2 = 1 & \mbox{digit} & 8 \\ \frac{ 8 }{ 1 } & 8^2 - 74 \cdot 1^2 = -10 & \mbox{digit} & 1 \\ \frac{ 9 }{ 1 } & 9^2 - 74 \cdot 1^2 = 7 & \mbox{digit} & 1 \\ \frac{ 17 }{ 2 } & 17^2 - 74 \cdot 2^2 = -7 & \mbox{digit} & 1 \\ \frac{ 26 }{ 3 } & 26^2 - 74 \cdot 3^2 = 10 & \mbox{digit} & 1 \\ \frac{ 43 }{ 5 } & 43^2 - 74 \cdot 5^2 = -1 & \mbox{digit} & 16 \\ \frac{ 714 }{ 83 } & 714^2 - 74 \cdot 83^2 = 10 & \mbox{digit} & 1 \\ \frac{ 757 }{ 88 } & 757^2 - 74 \cdot 88^2 = -7 & \mbox{digit} & 1 \\ \frac{ 1471 }{ 171 } & 1471^2 - 74 \cdot 171^2 = 7 & \mbox{digit} & 1 \\ \frac{ 2228 }{ 259 } & 2228^2 - 74 \cdot 259^2 = -10 & \mbox{digit} & 1 \\ \frac{ 3699 }{ 430 } & 3699^2 - 74 \cdot 430^2 = 1 & \mbox{digit} & 16 \\ \end{array}$$