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
_____________________________________________

Pell Pairs of Positive Integer Solutions

Date: 03/29/2012 at 12:26:42
From: B
Subject: Solving Quadratic Diophantine equations

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.

Start with

   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
  (quadratic) Diophantine equation
  (quadratic) number field

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 
   http://en.wikipedia.org/wiki/Quadratic_number_field 
   http://en.wikipedia.org/wiki/Quadratic_integer 

And so on.

If you have any questions about this or need more help, please write back
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

[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/