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
Math Forum Home || Math Library || Quick Reference || Math Forum Search