4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The first integer solution with $|x|>1$ is $x=\pm9801$. $\endgroup$ – Lucian Dec 1 '14 at 5:37
  • $\begingroup$ 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. $\endgroup$ – L887 Dec 1 '14 at 7:02
  • $\begingroup$ 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 $\endgroup$ – L887 Dec 1 '14 at 7:32
  • $\begingroup$ @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? $\endgroup$ – L887 Dec 1 '14 at 7:38
  • $\begingroup$ L887, I meant something rather different, equivalent to continued fractions, which you should learn in any case, continued fractions are quite easy. $\endgroup$ – Will Jagy Dec 1 '14 at 20:36
4
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ Thanks Will Jagy you are awesome ! :) $\endgroup$ – L887 Dec 4 '14 at 5:17
3
$\begingroup$

(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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.