Solving with the Pell Equation
Date: 11/15/2004 at 23:24:09 From: Matt Subject: Integer Solutions greater than 1000 to x^2-29y^2=7 In class we are discussing how to solve problems of the form x^2 - ny^2 = N for fixed (n,N). The process is fairly simple if |N| < n^(1/2); however, how does one find solutions if |N| > n^(1/2)? Specifically, how does one extract integer solutions to x^2 - 29*y^2 = 7 with x and y being integers greater than 1000? I can't think of a way to do it other then just writing a program to do it for me. The only thing I can think of is dividing by 7 to get an N < n^(1/2), but then that changes how the whole problem works.
Date: 11/16/2004 at 14:57:54 From: Doctor Vogler Subject: Re: Integer Solutions greater than 1000 to x^2-29y^2=7 Hi Matt, Thanks for writing to Dr. Math. Your question opens a door to a field of math that has been studied in great depth by some of the world's best mathematicians of years gone by (and a few of more recent years). It is more customary to use d instead of n, so I shall write your equation as x^2 - d*y^2 = N. It turns out that finding all solutions to this equation generally requires finding all solutions to the equation x^2 - d*y^2 = 1, which is known as the "Pell Equation" due to an error by Euler (he incorrectly attributed Pell with a method of solution of this kind of equation, and the name stuck). MathWorld is always a nice resource, so I'll provide a link to their page on the Pell Equation: Pell Equation http://mathworld.wolfram.com/PellEquation.html The history begins with Archimedes' Cattle Problem, back in ancient Greece. Here is the MathWorld page describing the problem. (It's not as colorful as some links, but it's descriptive.) Archimedes Cattle Problem http://mathworld.wolfram.com/ArchimedesCattleProblem.html But my favorite article on Archimedes' Cattle Problem is found on the following page: Solving the Pell Equation http://www.ams.org/notices/200202/200202-toc.html This covers the history of the Pell Equation, with the Cattle Problem being the main focus of the paper. It discusses the mathematics involved, but only at a level to understand the history rather than to really understand the mathematics. So it's a nice overview, very interesting, and not too dense. Then on the page Home Page for John Robertson http://hometown.aol.com/jpr2718/ there are several articles he wrote about solving the Pell Equation and solving the more general form of it that you gave, x^2 - d*y^2 = N, as well as solving the general second-order Diophantine equation, which is a*x^2 + b*xy + c*y^2 + d*x + e*y + f = 0 where a, b, c, d, e, and f are given integers, and we want all solutions in integers for (x, y). There are also a couple of answers from our own archives that use the Pell Equation, Proof Using Pell's Equation http://mathforum.org/library/drmath/view/53195.html Recurrence Relation for a Pell Equation http://mathforum.org/library/drmath/view/55938.html one of which gives a brief description of the continued fraction method. You might want to stop here, because the articles I mentioned on Home Page for John Robertson http://hometown.aol.com/jpr2718/ use none of the theory that I am about to describe, so you don't need to keep reading, but I think it helps understanding, so I will go on. It seems to me that the greatest amount of understanding in solving the equation x^2 - d*y^2 = N comes from the genre of mathematics known as "number fields," and real quadratic number fields in particular. Those are fields (as in abstract algebra's groups, rings, and fields) which are quadratic extensions of the rational numbers, namely Q[sqrt(d)]. A real quadratic number field consists of numbers of the form a + b*sqrt(d) where a and b are rational numbers. More important are the algebraic integers in this field, which are those elements that are roots of monic polynomials with integer coefficients. See also Algebraic Integer http://mathworld.wolfram.com/AlgebraicInteger.html It turns out that for most d (as long as d-1 is not divisible by 4), the algebraic integers in this field are those which have integers for a and b. (If d-1 is divisible by 4, then the algebraic integers are the ones for which a+b and 2a are integers, meaning that a and b can be half integers, but they have to be half integers together. This is why a 4 crops up in some equations, rather curiously. But let's ignore this for now.) So in this field, your equation factors as N = x^2 - d*y^2 = (x - y*sqrt(d))*(x + y*sqrt(d)). So all we have to do now is factor N into algebraic integers. The set of algebraic integers forms a ring that behaves rather like the integers do. It turns out that when d is positive (and not a square) then there are infinitely many units in this ring, and they consist of all powers of some so-called fundamental unit, times the various roots of unity in the ring (usually just 1 and -1). That is the Dirichlet Unit Theorem. That means that if we have any one solution, x^2 - d*y^2 = N, then we can multiply x + y*sqrt(d) by any power of the fundamental unit (a + b*sqrt(d))^k and get another solution (infinitely many more solutions). The fundamental unit is the smallest positive solution to x^2 - d*y^2 = +1 or -1. (But use +4 or -4 when d-1 is divisible by 4.) To get all solutions, we just do the above after factoring N in the ring of algebraic integers. Factoring bahaves a little funny, however, and depends quite a lot on the number d. Without going into too much detail, I will only say that you need to factor numbers in ideals. (Do you remember ideals from abstract algebra? This is where they came from and why they were invented.) There is a lot of math to learn here, so I would refer you to a text book. I learned from the book Number Fields by David A. Marcus, which I thought was very readable and quite understandable (after you've done abstract algebra), but there are many other books also available on the same subject. Finally, I'll get to the punch line: You have the equation x^2 - 29*y^2 = 7 so your quadratic number field is Q[sqrt(29)] and your Pell Equation is x^2 - 29*y^2 = +4 or -4. The smallest positive solution to this equation is x = 5, y = 1, which gives the fundamental unit u = (5/2) + (1/2)*sqrt(29) (It turns out that u^k has integers--not half integers--exactly when k is a multiple of 3. You can check this using a little modular arithmetic and recurrence relations for getting u^(k+1) from u^k.) Finally, we need to factor 7 in the number field. Prime numbers sometimes remain prime in a number field, but not always. In this case, it does not. In fact, (7) = (6 + sqrt(29)) * (6 - sqrt(29)). It might have happened that the factors had half-integers, in which case we would have to deal with other powers of u. But since they are integers, all solutions will be x + y*sqrt(29) = u^(3k) * (6 + sqrt(29)) and x + y*sqrt(29) = u^(3k) * (6 - sqrt(29)) where k is a (positive or negative) integer. If you pick large numbers for k, then x and y will be very large, even bigger than 1000. I should also point out that the "recurrence relations," that many of the links I provided will refer to, generally get from one equation to another by multiplying by (a power of) the fundamental unit. So, essentially you get from one solution to another by multiplying by u^3 = 70 + 13*sqrt(29). I hope all of this was interesting and helpful. I hope you enjoy some of those links I included. And I hope you learn some interesting mathematics as you work with these Pell Equations. I find this kind of thing fascinating, and I hope you do too. If you have any questions about this or need more help, please write back, and I will try to offer more advice. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum