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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum