Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/