Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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.

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search