Diophantine System of Equations
Date: 12/31/2004 at 15:09:42 From: John Subject: Diophantine problem - 2 equations, 3 variable, quadratic Please find the rational solutions (in parametric form) to the set of two simultaneous equations: x^2 + x = y^2 x^2 + 1 = z^2 The 1st equation has solutions x = 1 / (s^2 - 1), and the 2nd equation has solutions x = (1 - t^2) / 2t, but I can't find a parametric equation that solves both equations simultaneously. I do know that x = -4/3 is a particular solution. This question comes from pg. 194 of Oystein Ore's "Number Theory and Its History".
Date: 01/04/2005 at 17:40:05 From: Doctor Vogler Subject: Re: Diophantine problem - 2 equations, 3 variable, quadratic Hi John, Thanks for writing to Dr. Math. I haven't read the book you referred to, but that's a very interesting system of equations. Solving each of them separately allows you to write it as a single equation in two variables. Allow me to elaborate. You suppose that there are rational numbers (x, y, z) which satisfy x^2 + x = y^2 x^2 + 1 = z^2. First we assume that x is nonzero (and we already know that x=0 is a solution). Then we let s = y / x t = z - x. If we substitute these into our original equations, we find that x(x + 1 - s^2*x) = 0 1 = t(t + 2x) and therefore x = (1 - t^2) / (2t) and since x is nonzero, x = 1 / (s^2 - 1). In other words, whenever x is nonzero and x^2 + x and x^2 + 1 are both (rational) squares, there will be (rational) numbers s and t such that x = (1 - t^2) / (2t) x = 1 / (s^2 - 1). So every answer to your system of Diophantine equations has to satisfy (1 - t^2) / (2t) = 1 / (s^2 - 1). Furthermore, any rational solution to this last equation will give a solution to your problem. So all we have to do is solve this last equation. We can also write this as: s^2 = 1 + (2t)/(1 - t^2) = (t^2 - 2t - 1)/(t^2 - 1). So we just need to find all numbers t so that the fraction on the right is a square. Or we can let u = s(t^2 - 1) and then we have u^2 = (t^2 - 2t - 1)(t^2 - 1) and we just need to find all numbers t so that the polynomial (t^2 - 2t - 1)(t - 1)(t + 1) = t^4 - 2t^3 - 2t^2 + 2t + 1 gives a square. Now we have a single equation in two variables, which is a more normal kind of Diophantine equation. We want all rational solutions to u^2 = (t^2 - 2t - 1)(t^2 - 1). This equation has degree 4, which means that if it is nonsingular then it will have genus 3. It turns out that it *is* singular, which means that its genus is less than 3. Unfortunately, we're already getting close to the limit of what algebraic geometry I have learned, so I'm about to get stuck. In particular, I don't know how to check whether the genus is 0, 1, or 2. But I *think* that the genus is 2. And I don't really know enough about genus to tell you exactly what it is, more than to say it measures the degree of complexity of certain types of equations. Finally, I will tell you the reason that the genus is so important. It has been proven if your equation has genus zero, then you can write out all rational solutions as rational functions in one variable (like you did in your question). If the genus is bigger than zero, then you cannot write out all rational solutions in that way. But if the genus is one, then you can convert your equation into an elliptic curve, and the (very interesting) study of elliptic curves (of which I am more familiar) allows you to count the number of solutions, find a few "special" solutions, and get from the special solutions to all other solutions. Finally, if the genus is bigger than one, then it has been proven that there are only finitely many rational solutions. But I do not believe that there is an algorithm that will find them all, although there may be techniques that work for some kinds of equations. Last of all, I used the (free) math program GNU Pari, available for download at http://pari.math.u-bordeaux.fr/ to look for some rational solutions. The ones I found were x = 0 x = -4/3 x = 9/40 x = 400/561, and I checked all fractions a/b where |a| and |b| are less than 5000. If the genus is two, these may be all of the solutions. Or there might be a few more. 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/
Date: 01/06/2005 at 16:27:39 From: Doctor Vogler Subject: Re: Thank you (Diophantine problem - 2 equations, 3 variable, quadratic) Hi again, John, I have been having a hard time getting your question out of my head, and it resulted in my looking at it in a different way. I mentioned that I had my computer look for a few rational points. I found several. I was checking all values x = a/b where a and b were relatively small. But then I realized that it would be faster to solve one of the equations beforehand, so I used the fact that a^2 + b^2 is a square to conclude that a = r^2 - s^2 b = 2rs (or vice-versa) for some relatively prime pair (r, s) with one odd and one even. That generated answers much faster. But then it occurred to me that the remaining equation to check, which is that a(a + b) = (r^2 - s^2)(r^2 - s^2 + 2rs) is a square, can also be simplified. It turns out that the gcd of those two factors has to be 1. (The gcd must divide the difference, 2rs, but r^2 - s^2 is odd, and any odd prime factor of the gcd must divide either r or s, as well as r^2 - s^2, and therefore both r and s, contradicting that r and s are relatively prime.) That means that BOTH of them have to be squares. My first thought was to use r^2 - s^2 = t^2 to write r and s in terms of c and d (which gave me results still faster). But then I realized that if I solved the other equation first, r^2 - s^2 + 2rs = t^2 then I could see what the gcd of r + s and r - s is, and then continue this same pattern, perhaps indefinitely. To solve the last equation I wrote down, I used techniques like the one described in http://mathforum.org/library/drmath/view/65319.html and got r = cd + d^2 s = d^2 - c^2 + 2cd. But the answers that my computer was giving me (which are now really big numbers in a and b, although they come from small numbers in c and d) were starting to look like points on an elliptic curve. Rational points on an elliptic curve have numerators and denominators whose sizes (number of digits - i.e. logs) grow exponentially. This caused me to try a little harder to turn the equation I mentioned before, u^2 = (t^2 - 2t - 1)(t^2 - 1), into a cubic equation, or an elliptic curve. I remembered something about divisors of elliptic functions that I read somewhere (sorry; it was in a paper that is not publicly available, but I'm sure you could find it in a book on elliptic curves or algebraic geometry). I used that technique and a little bit of luck (I guess the luck was the only thing I really needed) to get the right transformation, which was actually quite simple: w = t^2 - u or u = t^2 - w. Then this turns our equation into (t^2 - w)^2 = (t^2 - 2t - 1)(t^2 - 1), and then the t^4 terms on both sides cancel, and we are left with w^2 - 2wt^2 = -2t^3 - 2t^2 + 2t + 1, which is a cubic equation! In fact, it is a nonsingular cubic, which means that, indeed, you have an elliptic curve. Unfortunately, putting it into standard form (Weierstrass form) is extremely difficult, since you need a "flex" point first (a point whose tangent intersects the curve with multiplicity three), and there are no rational flex points. That means you have to work in a number field. Unfortunately, it appears that the number field you have to work in has degree 12, which is rather high. That means that it might be hard to describe the structure of all of the solution points on the curve, but you can, however, still use elliptic curve techniques to find lots of solutions (which will get very large very quickly - that is, the numerators and denominators will get very large). The idea is to take two points that you already know are on the curve and draw the straight line between them. (Or, more accurately, write down the equation of the line between them.) This line has to intersect your cubic curve in exactly three points, and you already know two of them! So you just divide those out and get the third point. In fact, you can do the same thing with a single point by using the tangent line to the cubic curve at that point; a tangent line always intersects with multiplicity at least two, which means you can divide out that factor twice and get the third point. There is a group structure going on here, too, but the identity is not a point with rational coefficients (it's in that number field with degree 12 that I mentioned), so that makes using the group structure impractical. I was rather terse about how to get from point to point on the elliptic curve, and you might not be familiar with this technique. Here's an answer from our archives that I wrote which describes essentially how to do this very thing: Cubic Diophantine Equation in Three Variables http://mathforum.org/library/drmath/view/66650.html If it is confusing, or if you have trouble applying it to your curve, then please write back. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 02/24/2005 at 20:59:44 From: Doctor Vogler Subject: Re: Diophantine problem - 2 equations, 3 variable, quadratic Hi John, In case you're still interested, I have some more news on your question about the simultaneous Diophantine equations x^2 + x = y^2 x^2 + 1 = z^2 You'll recall that we set s = y / x t = z - x and found that x = (1 - t^2) / (2t) x = 1 / (s^2 - 1), as you pointed out in your first question. I pointed out that you can combine these to get the single equation (1 - t^2) / (2t) = 1 / (s^2 - 1) whose rational solutions give rational solutions to your original two equations. Then I modified this to s^2 = 1 + (2t)/(1 - t^2) = (t^2 - 2t - 1)/(t^2 - 1) and set u = s(t^2 - 1) so that our equation became u^2 = (t^2 - 2t - 1)(t^2 - 1) = (t^2 - 2t - 1)(t - 1)(t + 1) = t^4 - 2t^3 - 2t^2 + 2t + 1. Then I realized that I could make this equation into a cubic equation with the substitution w = t^2 - u u = t^2 - w, and this turned our equation into (t^2 - w)^2 = (t^2 - 2t - 1)(t^2 - 1) or w^2 - 2wt^2 = -2t^3 - 2t^2 + 2t + 1, which is cubic. I pointed out that this equation has no flex, so it could not be put into Weierstrass form. That was only partly correct. It's true that it doesn't have a flex, but it turns out that there is a slightly complicated but very clever way to put any cubic equation (even without a flex) into Weierstrass form. Furthermore, I stated that you could still use the concept of getting new points by intersecting lines with your curve, but there would be no group structure. That was completely wrong. I forgot that there is no need to be in Weierstrass form to make a group. So I will revise my comments. First of all, to form a group, all you need is one rational point. The point is generally denoted with the letter O (resembling the zero, since this point is your additive identity). You can choose any rational point on the curve, such as (3, 13) which corresponds to x = -4/3 (and y = 2/3, z = 5/3). For reasons that I will explain later, I will prefer to choose the point (0, 1, 0). You'll notice that I chose a point at infinity, which means that I had to switch to "projective coordinates" to describe the point. That means that we homogenize the equation and it becomes W^2*Z - 2WT^2 = -2T^3 - 2T^2*Z + 2T*Z^2 + Z^3. (It looks like I've switched the roles of capital letters and lowercase from the other message that I referred to, since I used capitals for affine coordinates there, and lowercase for projective, but that's reversed here.) Now you "multiply" points like I described in that other message, by intersecting the line through the two points with the curve, and taking for the product the third point of intersection. Note that this operation does NOT form a group. To "add" points, which is the operation that forms a group, you multiply them together, and then you multiply the product with the point O = (0, 1, 0). Then the identity (the zero) is the point O = (0, 1, 0). To take the negative of a point, you multiply it by (1, 1, 0), which happens (in your equation) to be the product of O with itself (in general, O is the identity and -Q = (OO)Q). The hard part is finding generators for the group. That is, you want to find points, such as P and Q so that every point is mP + nQ where m and n run over all of the integers. It takes a lot of work to determine how many generators are needed and what they are. Various algorithms exist, and a couple of programs, such as one called MWRANK (by John Cremona), but nearly all of them assume that your curve is in Weierstrass form. So what do you do? Well, that's where this other technique comes in. Rather than giving it in full generality (though I might take the time if you're interested), I will simply use the technique to convert your equation into Weierstrass form. I'm going to run through a lot of variables, so I hope you don't mind, but I'm going to use new names for the variables I've already used. I'll put the old names in parentheses so that you can follow where I'm going: We'll start with x^2 + x = y^2 x^2 + 1 = z^2 and then we'll write (was s) a = y / x (was t) b = z - x so that x = (1 - b^2) / (2b) x = 1 / (a^2 - 1) and we want to solve (1 - b^2) / (2b) = 1 / (a^2 - 1). Then we write (was u) c = a(b^2 - 1) so that our equation became c^2 = b^4 - 2b^3 - 2b^2 + 2b + 1. Next, we write (was w) d = b^2 - c to make our equation a cubic, which is where we got our elliptic curve d^2 - 2db^2 = -2b^3 - 2b^2 + 2b + 1. Now we need to make this curve Weierstrass. First we need (0, 0) to be a point on the curve, so we switch two of the projective variables (remember W, T, Z? We want to use W and Z instead of W and T). In affine coordinates, that amounts to setting e = b/d f = 1/d which turns our equation into f - 2e^2 = -2e^3 - 2e^2f + 2ef^2 + f^3. Next we set g = e - 1 h = f/g and then we take the big plunge and set u = -2/h - 1 v = [ -2(h^2 - 2h - 2) - 2(h^3 + 2h^2 - 2h - 2)g ]/h^2 which gives us out new equation in reduced Weierstrass form. All of the previous variable changes had degree one, which can't change things like flex points, but this higher-degree change creates a flex point. You can work out that this results in transforming your equation into v^2 = u^3 + u^2 - 9u + 7. From solution points of this equation, you can get back to the (b, d) cubic and then to the solutions (x, y, z) by reversing the above transformations: h = -2/(u + 1) g = (-2(h^2 - 2h - 2) - vh^2)/(2(h^3 + 2h^2 - 2h - 2)) f = gh e = g + 1 d = 1/f b = de c = b^2 - d a = c/(b^2 - 1) x = 1/(a^2 - 1) = (1 - b^2)/(2b) y = a/(a^2 - 1) z = (1 + b^2)/(2b). It turns out (and it surprised me) that these transformations, in each direction, are homomorphisms. But I imagine that this is probably true in general when you have rational transformations in both directions. So now we can send the above elliptic curve in Weierstrass form to MWRANK, and it tells us that the curve has torsion group Z/2Z and rank 1 (meaning only one generator needed other than the torsion), with generator (3, 4). Note that a curve in Weierstrass form is generally computed with the identity point O = (0, 1, 0). So we map the torsion point, the generator, and the identity back to the curve in b and d (or w and t), the one we had been working with before. We find that the identity maps to (0, 1, 0), which is why I chose that point before. The generator maps to (3, 5), although you can also use (-1/3, -1/3) or (-1, 1) or (1, 1) as generators. So if we write P = (3, 5) (that's affine form, or (3, 5, 1) in projective form) for our generator, and call the torsion point T = (0, 1) (or (0, 1, 1), which is called "torsion" because 2T = O), then we can compute all of the other points: ... ... -4P = (-5/4, 23/8, 1) -4P+T = (4/5, 37/25, 1) -3P = (3, 13, 1) -3P+T = (-1/3, 5/9, 1) -2P = (1, 1, 0) -2P+T = (0, -1, 1) -P = (-1, 1, 1) -P+T = (1, 1, 1) O = (0, 1, 0) T = (0, 1, 1) P = (3, 5, 1) P+T = (-1/3, -1/3, 1) 2P = (-5/4, 1/4, 1) 2P+T = (4/5, -1/5, 1) 3P = (-33/17, 137/17, 1) 3P+T = (17/33, 139/99, 1) 4P = (205/84, 1103/168, 1) 4P+T = (-84/205, 277/1025, 1) ... ... It turns out that (n-1)P, (n-1)P + T, (-n-1)P, and (-n-1)P + T all correspond to the same x value, by taking the four combinations of signs for y and z - i.e. (x, y, z) and (x,-y, z) and (x, y, -z) and (x, -y, -z). In this way, you can get all (infinitely many) rational solutions to your equation. If you have any questions about this, please write back and show me what you have been able to do, and I will try to offer further help. - 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.