Associated Topics || Dr. Math Home || Search Dr. Math

### Pell Pairs of Positive Integer Solutions

```Date: 03/29/2012 at 12:26:42
From: B

Find at least two pairs of positive integer solutions to this equation:

x^2 - 567y^2 = 1

I know the formula for Pythagorean triples, and have used it to solve
similar equations, but do not know how to do this one.

```

```
Date: 03/29/2012 at 16:34:11
From: Doctor Vogler
Subject: Re: Solving Quadratic Diophantine equations

Hi B,

Thanks for writing to Dr. Math.

This is an example of a Pell equation. Solutions to Pell equations are
harder to find than for Pythagorean triples, but there is a
strategy here.

In your case, you will definitely want to take advantage of the fact that
the square-free part of 567 is really quite small. You should write the
equation as

x^2 - 7(9y)^2 = 1

Then start by looking for solutions to the Pell equation

a^2 - 7b^2 = 1

Finally, decide which of those solutions have b divisible by 9.

Later, I'll refer you to some articles to explain why I do the following,
but you should start solving the Pell equation by checking all small
integer values for a and b until you find that the smallest non-trivial
unit in the quadratic number field Q(sqrt(7)) is

8 + 3*sqrt(7)

This means that all solutions to the equation ...

a^2 - 7b^2 = 1

... will have this form, for some integer k:

a + b*sqrt(7) = +/-(8 + 3*sqrt(7))^k

In particular, that means that you can put the solutions into a pair of
sequences (a_k, b_k) parametrized by all integers k. I'll describe one
sequence; the other is its negative.

a_0 = 1 and b_0 = 0

Go up with

a_(k + 1) = 8*a_k + 21*b_k
b_(k + 1) = 3*a_k + 8*b_k.

Alternately, go down with

a_(k - 1) =  8*a_k - 21*b_k
b_(k - 1) = -3*a_k + 8*b_k.

To decide which of these have b_k divisible by 9, just "step out" the
sequence mod 9. Since a and b can only take finitely many values mod 9, it
must necessarily repeat.

The sequence goes

(1, 0)
(8, 3)
(1, 3)
(8, 0)
(1, 6)
(8, 6)

Then it repeats, starting again with (1, 0). So b_k is divisible by 9 (is
0 mod 9) if and only if k is divisible by 3. So k = 3n, which means that
all solutions with b divisible by 9 have the form

a + b*sqrt(7) = +/-(8 + 3*sqrt(7))^(3n)

If you multiply out ...

(8 + 3*sqrt(7))^3 = 2024 + 765*sqrt(7),

... so that ...

a + b*sqrt(7) = (+ or -)(2024 + 765*sqrt(7))^n

... then you'll find that you can also make this into a sequence much like
the larger set of solutions:

a_(n + 1) = 2024*a_n + 5355*b_n
b_(n + 1) =  765*a_n + 2024*b_n

Of course, since y is just b/9, you can also write this as

x + y*9*sqrt(7) = +/-(2024 + 765*sqrt(7))^n

With x_0 = 1, y_0 = 1, and ...

x_(n + 1) = 2024*x_n + 48195*y_n
y_(n + 1) =   85*x_n + 2024*y_n

... you will find that this gives you as many solutions as you need. In
fact, it will give you all solutions (up to sign). You can also write out
the solutions explicitly (instead of with a recurrence relation) using the
facts that

x + y*9*sqrt(7) = (2024 + 765*sqrt(7))^n
x - y*9*sqrt(7) = (2024 - 765*sqrt(7))^n

Just add those two equations to solve for x, and subtract them to solve
for y. Multiply them to get your original equation.

For more details, you might want to search our archives for these kinds of
keywords:

Pell equation

For example, in our archives, you might be interested in

http://mathforum.org/library/drmath/view/66869.html
http://mathforum.org/library/drmath/view/66725.html

On Wikipedia, you might be interested in

http://en.wikipedia.org/wiki/Pell_equation

And so on.

and show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School 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