Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || 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/   
    
Associated Topics:
College Algorithms
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

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

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