Solving System of Equations Using Elliptic Curves
Date: 12/15/2006 at 13:45:22 From: Francisco Subject: System equations in Q (rational numbers) Find a rational number s such that s^2 + 7 and s^2 - 7 are both squares of rational numbers. I'm having trouble with 7, but here's how I would solve it for s^2 + 5 and s^2 - 5: Let x and y be the two rational numbers we are looking for so that s^2 + 5 = x^2 and s^2 - 5 = y^2. Then x^2 - y^2 = (x + y)(x - y) = 10 and letting x + y = a and x - y = 10/a we have 2x = a + 10/a = (a^2 + 10)/a where x = (a^2 + 10)/2a and y = (a^2 - 10)/2a. Then s^2 = x^2 - 5 = y^2 + 5 = (a^4 + 100)/4a^2 where we observe that a^4 + 100 must be the square of a rational number. If we set a^4 + 100 = (a^2 + b)^2 = a^4 + 2ba^2 + b^2 it is 100 = b^2 + 2ba^2 and a = sqrt((100 - b^2)/2b) where for b = 8 we have as much above as below two perfect squares and a = 6/4 = 3/2 with which x = 49/12, x^2 = 2401/144, s^2 = 2401/144 -5 = 1681/144 and s = 41/12.
Date: 12/15/2006 at 23:39:28 From: Doctor Vogler Subject: Re: System equations in Q (rational numbers) Hi Francisco, Thanks for writing to Dr. Math. You can solve the other equation in the same way, except that the hard part is how you figured out that b=8 gives a square for (100-b^2)/(2b). So let me explain something slightly different. It turns out that the intersection of two quadratic equations (i.e. simultaneous solutions to two polynomial equations of degree 2) in three variables is equivalent to an elliptic curve. Are you familiar with elliptic curves? You can see some of the process of turning a pair of equations like yours s^2 + 5 = u^2 s^2 - 5 = v^2 into a single elliptic curve at Diophantine System of Equations http://mathforum.org/library/drmath/view/67771.html You can also see a lot of how to compute points on elliptic curves, as well as another conversion into an elliptic curve, at Solving a Quartic Diophantine Equation http://mathforum.org/library/drmath/view/68354.html In your case, it turns out that for any number t (such as t=5 or t=7) the two equations s^2 + t = u^2 s^2 - t = v^2 are equivalent to the elliptic curve y^2 = x^3 - 16(t^2)x. The translation between them is as follows: If t is nonzero, then the number a = u+v cannot be zero, so we can map a solution (s, u, v) to x = 8t(as + t)/a^2 y = 32t^2(as + t)/a^3 = 4tx/a. Furthermore, any point on the elliptic curve except for the three points that have y=0 (namely x=0, x=-4t, and x=+4t) come from the solution s = (2x^3 - y^2)/(4xy) u = (y^2 + 8tx^2)/(4xy) v = (y^2 - 8tx^2)/(4xy). Well, something about the structure of elliptic curves is described on the second link I mentioned (Solving a Quartic). It turns out that your elliptic curve always has the three period-two points (0, 0) (0, 4t) (0, -4t). For many values of t, these are the only rational points on the curve, implying that there are no solutions to your simultaneous equations. But for t=5 and also for t=7, the curve has rank 1. For t=5, a generator is the point (-16, -48). For t=7, a generator is the point (100, 960). I computed these using MWrank. To see what this means, you can compute in Pari as follows. Set up the curve with something like t=7 e=ellinit([0,0,0,-16*t^2,0]) The three period-two points are a=[0,0] b=[4*t,0] c=elladd(e,a,b) For t=7, the generator is p=[100,960] Now you can compute the (s, u, v) coordinates as follows: q=p x=q y=q u=(y^2+8*t*x^2)/(4*x*y) v=(y^2-8*t*x^2)/(4*x*y) s=(2*x^3-y^2)/(4*x*y) You get the solution that you were looking for. Are there others? You can try adding a period-two point as follows: q=elladd(e,p,a) x=q y=q u=(y^2+8*t*x^2)/(4*x*y) v=(y^2-8*t*x^2)/(4*x*y) s=(2*x^3-y^2)/(4*x*y) You'll find that this only changes the signs of u, v, and s. It's the same for b and c. But if you add p to itself, you get more: q=elladd(e,p,p) x=q y=q u=(y^2+8*t*x^2)/(4*x*y) v=(y^2-8*t*x^2)/(4*x*y) s=(2*x^3-y^2)/(4*x*y) In fact, you can find lots of solutions by changing the number 3 in the following to whatever you'd like: q=ellpow(e,p,3) x=q y=q u=(y^2+8*t*x^2)/(4*x*y) v=(y^2-8*t*x^2)/(4*x*y) s=(2*x^3-y^2)/(4*x*y) I'll bet you never would have found those solutions without using elliptic curves! 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