# Finding all solutions to $y^3 = x^2 + x + 1$ with $x,y$ integers larger than $1$

I am trying to find all solutions to

(1) $y^3 = x^2 + x + 1$, where $x,y$ are integers $> 1$

I have attempted to do this using...I think they are called 'quadratic integers'. It would be great if someone could verify the steps and suggest simplifications to this approach. I am also wondering whether my use of Mathematica invalidates this approach.

My exploration is based on a proof I read that $x^3 + y^3 = z^3$ has no non-trivial integer solutions. This proof uses the ring Z[W] where $W = \frac{(-1 + \sqrt{-3})}{2}$. I don't understand most of this proof, or what a ring is, but I get the general idea. The questions I have about my attempted approach are

1. Is it valid?
2. How could it be simplified?

Solution:

Let $w = (-1 + \sqrt{-3})/2$. (Somehow, this can be considered an "integer" even though it doesn't look anything like one!)

Now $x^3 - 1 = (x-1)(x-w)(x-w^2)$ so that, $(x^3 - 1)/(x-1) = x^2 + x + 1 = (x-w)(x-w^2)$. Hence

$y^3 = x^2 + x + 1 = (x-w)(x-w^2).$

Since $x-w, x-w^2$ are coprime up to units (so I have read) both are "cubes". Letting $u$ be one of the 6 units in Z[w], we can say

$x-w = u(a+bw)^3 = u(c + dw)$ where

$c = a^3 + b^3 - 3ab^2, d = 3ab(a-b)$

Unfortunately, the wretched units complicate matters. There are 6 units hence 6 cases, as follows:

1) $1(c+dw) = c + dw$

2) $-1(c+dw) = -c + -dw$

3) $w(c+dw) = -d + (c-d)w$

4) $-w(c+dw) = d + (d-c)w$

5) $-w^2(c+dw) = c-d + cw$

6) $w^2(c+dw) = d-c + -cw$

Fortunately, the first two cases can be eliminated. For example, if $u = 1$ then $x-w = c+dw$ so that $d = -1 = 3ab(a-b).$ But this is not possible for integers $a,b$. The same reasoning applies to $u = -1$.

For the rest I rely on a program called Mathematica, which perhaps invalidates my reasoning, as you will see.

We attack case 5. Here

$x = c-d = a^3 + b^3 - 3a^2b$, and $c = a^3 + b^3 - 3ab^2 = -1.$

According to Mathematica the only integer solutions to $c = -1$ are $(a,b) = (3,2), (1,1), (0,-1), (-1,0), (-1,-3), (-2,1).$

Plugging these into $x = c-d$ we find that no value of x that is greater than 1. So case 5 is eliminated, as is 6 by similar reasoning.

Examining case 4 we see that $d-c = -(a^3 + b^3 - 3a^2*b) = -1$ with solutions $(-2,-3), (-1,-1), (-1,2), (0,1), (1,0), (3,1).$

Plugging these values into $x = d = 3ab(a-b)$ yields only one significant value, namely $x = 18$ (e.g. (a,b)=(3,1) . The same result is given by case 4. Hence the only solution to (1) is $7^3 = 18^2 + 18 + 1$

However, I'm unsure this approach is valid because I don't know how Mathematica found solutions to expressions such as $a^3 + b^3 - 3ab^2=-1$. These seem more difficult than the original question of $y^3 = x^2 + x + 1$, although I note that Mathematica could not solve the latter.

-
I don't know why... but I must say I genuinely liked your approach. What exactly compelled you to do that initial treatment with the w? – frogeyedpeas Jun 17 '13 at 15:14
You probably want to learn bits and pieces of algebraic integers (grab a book on algebraic number theory) and elliptic curves. Fun topics. Start out innocent enough but do run deep (if you don't stop). – Jyrki Lahtonen Aug 19 '14 at 20:44
Are you interested in any simpler solution (i.e., a whole new method), or only simplifications of this approach? – Kieren MacMillan Aug 19 '14 at 20:46
$y^3=x^2+x+1$ if and only if $(4y)^3=(4(2x+1))^2+48$. But $a^3=b^2+48$ has $2$ integer solutions (see oeis.org/A081120, in particular oeis.org/A081120/b081120.txt) $(a,b)=(4,\pm 4)$, so $(x,y)=(-1,1),(0,1)$ are all the solutions. – user236182 Oct 17 '15 at 21:45

Your proof is basically valid, but there are special circumstances for this particular ring of (algebraic) integers. You first need to check that $y$ can't be divisible by $3.$ Note that ( in the usual ring of integers), if we have $3$ divides $1 + x + x^{2},$ then we must have $x \equiv 1$ (mod $3$),say $x = 3z+1$ for some integer $z.$ Then $x^{2}+x +1 = 9z^{2} +9z+3,$ which is not divisible by $9,$ so $y$ is not divisible by $3.$ You are implicitly using the fact that $R = \mathbb{Z}[\omega]$ is a unique factorization domain. This is true- it is a principal ideal ring, in fact a Euclidean ring, where we define $d(a+b\omega) = a^{2}-ab +b^{2}.$ It is true, but not completely straightforward to prove, that if $u,v \in R,$ we may write $v = qu +r$ where $q,r \in R$ and either $r=0$ or $d(r) <d(u).$ The ring $R$ is sometimes known as the ring of Eisenstein integers. This $d$ function allows the usual theory of primes and unique decomosition of non-units as products of primes as developed by Euclid in the usual integers to proceed with little change (hence the expression Euclidean ring). There are, however, many rings of algebraic integers for which uniqueness of factorization fails, so this is a rather special situation. Anyway, your conclusion that $y^{3} = x^{2}+x+1 = (x-\omega)(x-\omega^{2})$ implies that $x-\omega = u(a+b\omega)^{3}$ for some unit $u$ and integers $a$ and $b$ is correct -as long as you know that $x - \omega$ and $x-\omega^{2}$ have no (non-unit) common factor in $R$. This is, in fact, true- anything which divides both $x- \omega$ and $x - \omega^{2}$ must divide $\omega - \omega^{2} = (x - \omega^{2})- (x-\omega).$ However $(\omega - \omega^{2})(\omega^{2}- \omega) = 3$, so $\omega - \omega^{2}$ does not factor further in $R$ (apart from unit factors). However, $\omega - \omega^{2}$ does not divide $y$ in $R,$ or else $3$ would divide $y^{2}$ in $\mathbb{Z},$ which we know it does not. The theory behind knowing how Mathematica finishes from this point is explained in other answers, though I believe it should be possible to devise a direct proof within $R$.

-

I have not verified your work. This is just to say that $y^3=x^2+x+1$ is the equation of an elliptic curve (with $j$-invariant equal to $0$). Using Sage or Magma, you can find that this elliptic curve has rank $1$ and trivial torsion subgroup. The group of rational points is generated by the point $P=(0,1)$, and the rest of the rational points are all the multiples of $P$:

\begin{align*} & \vdots \\ -3P &=\left(-\frac{703}{216},\frac{73}{36}\right)\\ -2P &=\left(18 , 7 \right)\\ -P &=\left(-1,1\right)\\ 0 & = \infty\\ P &=\left(0,1\right)\\ 2P &=\left(-19 , 7\right)\\ 3P &=\left(\frac{487}{216},\frac{73}{36}\right)\\ &\vdots \end{align*} Now one can use the rest of the theory of elliptic curves to show that the only integral points are $(18,7)$, $(-1,1)$, $(0,1)$, and $(-19,7)$. So the only solution $(x,y)$ with $x,y>1$ is $(18,7)$ as you found.

-
I appreciate your response, though it is far too advanced for my level of understanding. Your approach appears much simpler than my own. I do wish someone would verify that my use of "strange integers" is correct. I take it that Sage/Magma are tools similar to Mathematica which perhaps raises my original question: in what ways can we use such tools as part of a proof and still consider the proof valid? – Nick Aug 4 '12 at 11:05
As a matter of fact, the coefficients of this curve are small enough that one can run manually the so-called "method of descent" and prove everything I mentioned by hand, without the need of a computer algebra package. – Álvaro Lozano-Robledo Aug 4 '12 at 11:31
@BarryCipra Fixed it! Thanks for noticing! – Álvaro Lozano-Robledo Aug 20 '14 at 2:14

As far as I can tell — with the qualification that I'm shaky on "strange integers" as well — I believe your solution and use of quadratic integers is correct and valid.

As to your embedded question about the use of computer applications in a proof or solution... It in no way invalidates your approach. However, there are several things to consider.

1. If you use algebra to reduce your original equation to another equation, and then rely on a computer application to find solutions of that new equation, you are simply off-loading — or, more likely, up-loading — effort to the application. That application may use extremely complex algorithms, or bounds which rely upon complicated mathematical proofs and theorems, in order to give you solutions. Hence you may have made the method more complicated than it seems at first, and possibly more complicated than it needs to be.

2. Methods aided by computer applications require verification of the application algorithm before the result can be fully validated. In many cases — like yours, where you have [assumedly] used a well-known, documented, and verified function in a widely-used application to determine a “complete set of solutions” — this step is easy (and usually assumed). In the case where you might have developed your own functions or full program to do the math, the application code and algorithms themselves would have to be independently validated before your result could be accepted.

-

In this answer to a related thread, I outline a very elementary solution to this problem. There are probably even simpler ones, but I thought you might appreciate seeing that.

-