Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Back to Algorithms || Dr. Math Home || Search Dr. Math
_____________________________________________

Solutions for Pell's Equation


Date: 12/11/2000 at 03:20:29
From: Paul Weber
Subject: Pell's equation

I've been trying to find answers to Pell's equation (x^2 - Dy^2 = 1) 
for different D's, but I'm really having a problem. I've been looking 
in books and I simply don't understand some things such as the sqrt(D) 
convergents, or continued fraction expansion. If someone could explain 
this in layman's terms, I'd really appreciate it.

Paul


Date: 12/11/2000 at 14:48:47
From: Doctor Rob
Subject: Re: Pell's equation

Thanks for writing to Ask Dr. Math, Paul.

Your request is difficult to comply with, because solutions are 
intimately tied up with fractions close to the square root of D. That 
is because:

     x^2 - D*y^2 = 1
         x^2 - 1 = D*y^2
     (x^2-1)/y^2 = D
         sqrt(D) = sqrt(x^2-1)/y

and for moderate sizes of x, sqrt(x^2-1) is approximately equal to 
sqrt(x^2) = x, so sqrt(D) is approximately x/y.

Here is an algorithm for computing solutions, without an explanation 
of why it works, which you seem not to want.

0. Given: positive integer D, not a perfect square.

1. Initialize a(0) as the largest integer such that a(0)^2 < D;

      P(0) = 0
      Q(0) = 1
     A(-1) = 1
      A(0) = a(0)
     B(-1) = 0
      B(0) = 1
         i = 0

2. Compute

     P(i+1) = a(i)*Q(i) - P(i)

     Q(i+1) = (D-P(i+1)^2)/Q(i)
            = Q(i-1) + a(i)*(P(i)-P(i-1))

3. If Q(i+1) = 1 and i is odd, output the pair (A(i),B(i)), and stop.

4. Divide P(i+1)+a(0) by Q(i+1) getting integer quotient a(i+1).

5. Compute

     A(i+1) = a(i+1)*A(i) + A(i-1)
     B(i+1) = a(i+1)*B(i) + B(i-1)

6. Increase the value of i by 1 and and go back to Step 2.

When you stop, the output of this algorithm is the smallest positive 
solution (x,y).

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

Submit your own question to Dr. Math

Privacy Policy

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2002 The Math Forum
http://mathforum.org/dr.math/