Solving a Nonlinear Diophantine Equation
Date: 10/30/2005 at 23:49:00 From: Shane Subject: find integer solutions for x and y Given x^3 = 3y^2 + 3y + 1 where x < y, are there integer solutions for x and y?
Date: 11/01/2005 at 11:19:07 From: Doctor Vogler Subject: Re: find integer solutions for x and y Hi Shane, Thanks for writing to Dr. Math. This is called a (nonlinear) Diophantine equation. When there are no integer solutions, you can usually (although not always) prove this by considering the equation mod m, for some integer m. (This is called the Hasse principal.) But there are two integer solutions to your equation, namely (1,0) and (1,-1). That makes proving that there are no other integer solutions much harder. There are at least two other ways to attack this kind of a problem, and these use techniques from advanced number theory. One method is to use the theory of elliptic curves. In your case, this works rather well. In one sense, an elliptic curve is a cubic equation in two variables, such as yours. There is a way to "add" two points on the curve and get a third point, which operation has some nice properties; it forms a group. A theorem called Mordell's Theorem says that all of the rational points on an elliptic curve can be written as sums of points (generators) from a finite collection, usually quite small. This is true even when there are infinitely many rational points (for example, adding a point to itself k times might give you a different result for every integer k). There are algorithms for finding these generators (such as a program called mwrank, by John Cremona), and if it turns out that there are only finitely many points, then your search ends there. It turns out that your elliptic curve has only two rational points, which are the two I already mentioned. In the case that there are infinitely many rational points, you're still not completely out of luck; it's just a little harder. It has been proven that every elliptic curve has only finitely many integer points, and just a few years ago, some people came up with an algorithm that will find all integer points on an elliptic curve. I don't know of this algorithm being implemented in a publicly available program, but it could be done soon. Unfortunately, the algorithm is somewhat complicated, and not well suited to doing by hand. You can learn a little about elliptic curves from Cubic Diophantine Equation in Three Variables http://mathforum.org/library/drmath/view/66650.html or by searching our archives or the Internet for "elliptic curve." But a book on the subject would probably serve you best. The other method that comes to mind uses the theory of number fields (imaginary quadratic number fields, in particular). It is better suited to working out the solution by hand, though it doesn't work with all equations, and it takes some work. But it can work for yours. The idea is to factor the right side of your equation. Well, it doesn't factor over the integers, but it does factor (using the quadratic equation, for example). You get 3x^3 = (3y + 3/2 + sqrt(-3)/2)(3y + 3/2 - sqrt(-3)/2). It turns out that many of the same properties of prime factorization and the like work in the number field consisting of numbers of the form a + b*sqrt(-3) where a and b are rational. The "integers" (we call them algebraic integers) in this number field are the numbers with 2a, 2b, and a+b integers. (So (1+sqrt(-3))/2 is an algebraic integer, but 1/2 is not.) Next, we consider the factorization on the right side of your equation. The GCD (greatest common divisor) of the two algebraic integers must divide their difference, which is sqrt(-3), which happens to be a prime in your number field. That means that either the two factors are relatively prime, or their only common factor is sqrt(-3). That (almost) means that either one is a cube and the other is three times a cube, or both of them are cubes times sqrt(-3). I say almost because we also have to deal with units (like -1). It turns out that all of the units in your number field are the six powers of u = (1 + sqrt(-3))/2, which has u^2 = u-1, u^3 = -1, u^4 = -u, u^5 = 1-u, u^6 = 1. So actually you have six cases (or rather twelve, by reversing the two factors in the following pairs): (r^3) * (3s^3) (ur^3) * (3u^2s^3) (u^2r^3) * (3us^3) (sqrt(-3)r^3) * (sqrt(-3)s^3) (sqrt(-3)ur^3) * (sqrt(-3)u^2s^3) (sqrt(-3)u^2r^3) * (sqrt(-3)us^3) Then the idea is to consider that r = a + b*u where a and b are integers (remember the form of algebraic integers that I described above) and similarly for s. Write out the form of each of the factors above, such as ur^3 = (rational number) + (rational number)*sqrt(-3) and then see if the coefficient of sqrt(-3) could possibly be 1/2 or -1/2. You can learn a little about number fields from Solving with the Pell Equation http://mathforum.org/library/drmath/view/66869.html and Quadratic Polynomial Number Theory and Number Fields http://mathforum.org/library/drmath/view/65773.html or by searching our archives or the Internet for the phrase "number field", but a book would probably serve you best. Finally, it did occur to me that you can rearrange your equation and factor it differently like (x - 1)(x^2 + x + 1) = 3y(y + 1). The nice thing is that you don't have to resort to number fields. But I'm not sure what I would do with this equation, or if it would even help. I guess I would start by considering what the gcd of x-1 and y could be, and the gcd of x-1 and y+1. Then see if that helps me at all. But I'm not sure that it will. 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- The Math Forum at NCTM. All rights reserved.