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[1]
  y=q[2]
  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[1]
  y=q[2]
  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[1]
  y=q[2]
  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[1]
  y=q[2]
  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/