Proof Using Pell's Equation

Date: 09/18/1999 at 04:49:02
From: Tran Nam Dung
Subject: Continued fractions

Solving the Pell equation x^2 - Dy^2 = 1 for different D, finding the 
minimal solution (x0,y0) by using continued fractions, I determined 
that if

                              1
     Sqrt(D)= a1 + -----------------------
                                1
                   a2 + ------------------
                       a3 + ...
                                      k
                             an + ---------
                                  sqrt(D)+t

and 

     p/q = [a1;a2;...;an]

then

     p^2 - D.q^2 = (-1)^n.k

I tried to prove this fact, but couldn't. Please help me with 
instructions or some hints. Thanks a lot.

Namdung (Viet Nam)

Date: 09/18/1999 at 11:01:19
From: Doctor Anthony
Subject: Re: Continued fractions

I'll be using the notation x^2 - d.y^2 = 1  for Pell's equation.

We must show that if p/q is a convergent of the continued fraction 
expansion of sqrt(d) then x = p, y = q is a solution of one of the 
equations

     x^2 - d.y^2 = k

where  |k| < 1 + 2.sqrt(d)

If p/q is a convergent of sqrt(d) then we have:

     |sqrt(d) - p/q| < 1/q^2     (a property of convergents)

and multiplying through by q:

     |p - q.sqrt(d)| < 1/q   .................................(1)

but

     |p + q.sqrt(q)| =  |(p - q.sqrt(q)) + 2q.sqrt(d)|

                     <= |p - q.sqrt(d)| + |2q.sqrt(d)|

                     <  1/q + 2q.sqrt(d)
                     <  (1 + 2.sqrt(d))q 

So
     |p + q.sqrt(d)| <  (1 + 2.sqrt(d)).q  ...................(2)

Combining the inequalities (1) and (2) we get:

     |p^2 - d.q^2| = |p - q.sqrt(d)|.|p + q.sqrt(d)|

                   < (1/q)(1 + 2.sqrt(d)).q = 1 + 2.sqrt(d)

In general not all the convergents p(n)/q(n) of sqrt(d) give solutions 
to x^2 - d.y^2 = 1, but the above reasoning gives us information about 
the size of the values taken on by the sequence p^2 - d.q^2.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/