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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.