# Find all integer solutions: $x^4+x^3+x^2+x=y^2$

Find all integer solutions of the following equation: $$x^4+x^3+x^2+x=y^2$$

-
Can you factor the left hand side? – Jyrki Lahtonen Jan 2 '14 at 10:58
y is even, and x is either odd, or a multiple of $4$. – Lucian Jan 2 '14 at 12:09

When $|x|>1$ we have $$(2x^2+x)^2<4(x+x^2+x^3+x^4)<(2x^2+x+1)^2.$$

-
+1 what a simple and beautiful argument! – achille hui Jan 4 '14 at 0:12
@achillehui Thank you, but I can't take credit. I learned this trick from Ed Burger's book The Number Jungle. – Byron Schmuland Jan 4 '14 at 0:21
+1 Learned a new trick today! May I ask if these types of techniques have a name? =D – Yong Hao Ng Jan 4 '14 at 1:14
@YongHaoNg I don't know if it has a special name. I suppose it only works on very special Diophantine equations, but it is certainly worth knowing! – Byron Schmuland Jan 4 '14 at 1:46
I see, I was wondering if the book has a name for it. Thanks~ =D – Yong Hao Ng Jan 4 '14 at 1:49

The equation

$$y^2 = x^4 + x^3 + x^2 + x = x(x+1)(x^2+1)\tag{*1}$$

has four trivial solutions over $\mathbb{Z}\times\mathbb{Z}$:

$$(x,y) = (-1,0), (0, 0),(1,\pm 2)$$

To determine whether there are other non-trivial solutions, let's look at an equivalent problem:

$$y^2 = \begin{cases} z(z + 1)(z^2 + 1), &\text{ for } z = x \ge 2\\ z(z - 1)(z^2 + 1), &\text{ for } z = -x \ge 2\tag{*2} \end{cases}$$

Notice $$\gcd(z(z\pm 1),z^2+1) = \gcd( \pm z - 1, z^2 + 1) = \gcd(\pm z - 1,2) = 1 \text{ or } 2$$

Any solution of $(*2)$ must have one of the following two factorizations:

$$\begin{cases} z(z\pm 1) &= p^2,\\ z^2 + 1 &= q^2,\\ y &= \pm pq;\end{cases} \quad\text{ or }\quad \begin{cases} z(z\pm 1) &= 2p^2,\\ z^2 + 1 &= 2q^2,\\ y &= \pm 2pq.\end{cases}\quad\text{ with } \gcd(p,q) = 1.$$

We can rule out the factorization on the left because for $z \ge 2$, $z^2 + 1$ is never a square. For the factorization on the right, we can rewrite the $x$ part as

$$\left\{\begin{array}{ccrl} (2 z \pm 1 )^2 &-& 8p^2 &= 1\\ z^2 &-& 2q^2 &= -1 \end{array}\right.\tag{*3}$$

Define $A, B : \mathbb{Z} \to \mathbb{Z}$ by

$$A(k) + B(k) \sqrt{2} = (1+\sqrt{2})^k$$

It is known the positive integer solutions of Diophantine equations like those in $(*3)$ has the form

$$\left\{\begin{array}{ccl} 2 z\pm 1 &=& A(2m)\\ 2p &=& B(2m)\\ z &=& A(2n-1)\\ q &=& B(2n-1)\\ \end{array}\right. \quad\quad\text{ for } m , n \in \mathbb{Z}_{+}.$$ It is clear $2 z \pm 1 \ge z \implies 2m \ge 2n-1$. Notice $\frac{A(k+1)}{A(k)} \to 1+\sqrt{2} > 2$ as $k \to \infty$. For any $n$ large enough such that $A(2n) > 2 A(2n-1) + 1$, there are no way to find a $m$ to satisfy $(*3)$. A brute force computation shows that this happens as early as $n \ge 2$.

This leaves us the cases $n = 1$. It is easy to check for $n = 1$, one can choose $m = 1$ to make $(*3)$ works. However,

$$m = n = 1 \quad\implies\quad \left\{\begin{array}{ccl} 2 z\pm 1 &=& A(2) = 3 \\ 2p &=& B(2) = 2\\ z &=& A(1) = 1\\ q &=& B(1) = 1\\ \end{array}\right. \quad\iff\quad (x,y) = (1,\pm 2)$$ corresponds to a pair of trivial solutions we have covered before. The conclusion is aside from the four trivial solutions, $(*1)$ doesn't have any non-trivial solution.

-

The following shows that the only solutions are $$(0,0),(-1,0),(1,2),(1,-2)$$ by using a birational transformation to an Elliptic curve.

1. Birational transformation to an Elliptic curve

Denote $$C: v^2-u^4-u^3-u^2-u=0$$ It is clear that if $u=0$, then $v=0$. For the other case, $u\neq 0$, we can divide by $u^4$: $$\dfrac{v^2}{u^4}-1-\dfrac{1}{u}-\dfrac{1}{u^2}-\dfrac{1}{u^3}=0$$ Rearranging: $$\left(\dfrac{v}{u^2}\right)^2=\left(\dfrac{1}{u}\right)^3+\left(\dfrac{1}{u}\right)^2+\left(\dfrac{1}{u}\right)+1$$ Which is in fact an Elliptic curve: $$E: Y^2=X^3+X^2+X+1$$ In other words, we have a birational transformation $\phi$: \begin{align*} \phi: C &\to E\\ (u,v) &\mapsto \left(\dfrac{1}{u},\dfrac{v}{u^2}\right) = (x,y) \end{align*} (We know this type of transformation exists since we can compute genus of $C$ to be 1.)

If $(u,v)\in \Bbb Z^2$ is an integer solution for $C$, then $\left(\dfrac{1}{u},\dfrac{v}{u^2}\right)$ is a rational point on $E$.

In other words, it suffices to find all rational points of the form $\left(\dfrac{1}{u},\dfrac{v}{u^2}\right)$ on $E$.

In particular, notice that $\dfrac{1}{u}$ has numerator $1$ which is very restrictive. We shall make use of this constraint to make our main deduction.

2. Rational points on $E$

Using Sage, we find that the Mordell-Weil group over $\Bbb Q$ has the structure $$E(\Bbb Q)\cong \Bbb Z_2\times \Bbb Z$$ Where the order two torsion is $P=(-1,0)$ and the free group generator is $Q=(0,1)$.
In other words all rational points are written as: $$E(\Bbb Q)=[a]P\oplus [b]Q, \;\;\;\; (a,b)\in [0,1]\times \Bbb Z$$

Clearly $Q$ does not correspond to a solution. On the other hand, $P=(-1,0)$ has $x$-numerator 1. Hence we let $u=-1$: $$v^2=(-1)^4+(-1)^3+(-1)^2+(-1)=0,$$ and we find a solution in $C$: $$(u,v)=(-1,0)$$

3. A useful lemma

We shall be using this later:

If $(X,Y)\in E(\Bbb Q)$, then: $$(X,Y)=\left(\dfrac{m}{e^2},\dfrac{n}{e^3}\right)$$ for some $$m,n,e\in \Bbb Z,\;\;\;\;\gcd(m,e)=\gcd(n,e)=1$$ (This can be shown using $p$-adic valuations.)

4. Solving the main problem

We have seen that $Q=(0,1)$ does not correspond to a solution. Similarly, $$[2]Q=\left(\dfrac{-3}{4}, \dfrac{-5}{8}\right)$$ so that $[2]Q$ also does not correspond to a solution.

Now let $R=P$ or $R=[a]Q, a\geq 2$. We want to show that $R\oplus Q$ cannot correspond to a solution. Then by induction $$\{P\oplus [a]Q,[a]Q\;|\;a\geq 1\}$$ cannot be a solution and we would have covered $[r]P\oplus [s]Q, (r,s)\in [0,1]\times \Bbb N$.

Since $R\neq Q$, we can derive a formula for point addition with $Q$: $$R\oplus Q=\left(\dfrac{2+x-2y}{x^2},\dfrac{4 + 3 x + 2 x^2 + x^3 - 4 y - x y}{x^3}\right)$$

Recall that if indeed some $(u,v)$ maps to a rational point in $E$, then the $x$-coordinate satisfies: $$x(R\oplus Q)=\dfrac{2+x-2y}{x^2}=\dfrac{1}{u}$$ Now using our lemma in (3): $$\dfrac{2+x-2y}{x^2}=\dfrac{2+(m/e^2)-2(n/e^3)}{(m/e^2)^2}=\dfrac{1}{u}$$ $$\dfrac{(2e^3+me-2n)e}{m^2}=\dfrac{1}{u}$$ From which we draw the conclusion that $$e|m^2$$ Since $\gcd(m,e)=1$, this can only happen if $e=\pm 1$. Either way, this implies that $(x,y)=(m/e^2,n/e^3)$ are integral points.

(Perhaps can be solved without needing this information, but quite tedious.)

Sage tells us that the only integral points are $$(-1, 0), (0,\pm 1), (1,\pm 2), (7,\pm 20)$$ of which $(0,\pm 1)=\pm Q$ is not possible by construction of $R$.

Individual checking of the rest tells us that only $(-1,\pm 0),(1,\pm 2)$ results in $u=\pm 1$. We have seen the case $u=-1$ in section (2). For $u=1$:: $$v^2=1^4+1^3+1^2+1=4$$ From which we deduce $v=\pm 2$. Thus far we have the points $$(u,v)\in \{(0,0),(-1,0),(1,2),(1,-2)\}$$

From the induction, we conclude that there are no other possible candidates corresponding to \begin{align*} R &=P\oplus [a]Q, a\geq 1\\ R &= [a]Q, a\geq 1 \end{align*}

It remains to cover the rest of the cases. Since $P$ is order two, $[-1]P=P$. Then immediately $$P\oplus [a]Q = [-1]P\oplus [a]Q, a\geq 0$$ so that these are also not solutions.

The inverse of a point does not change the $x$-coordinates: $$-(x,y)=(x,-y)$$ Therefore if $R$ is not a solution, then $-R$ is also not a solution. This shows that $$-(P\oplus [a]Q)=[-1]P\oplus [-a]Q=P\oplus [-a]Q$$ $$-([a]Q)=[-a]Q, a\geq 1$$ are not solutions.

Therefore we have covered all the cases and we are done.

5. Sage codes for reference

E = EllipticCurve([0,1,0,1,1]);
tor = E.torsion_points();
rank = E.rank();
gens = E.gens();
integralPoints = E.integral_points();

-

EDIT : The case (1) in my answer has a big mistake. The case (2) is true.

$(x,y)=(0,0)$ is one of the solutions. In the following, suppose that $(x,y)\not=(0,0).$

We have $$x(x+1)(x^2+1)=y^2.$$ First, we know that $x$ and $x+1$ are coprime, and that $x$ and $x^2+1$ are coprime, too. This leads that there is an integer $k$ such that $x=k^2.$ (see the right hand side)

In the following, we break up the answer into two cases.

(1) The case that $x+1$ and $x^2+1$ are not coprime.

Letting $$x+1=ps,x^2+1=pt\ \ (\text{p is a prime number, s,t\in\mathbb Z})$$ we have $$(ps-1)^2+1=pt\iff p(t-ps^2+2s)=2\Rightarrow p=2.$$ So, we know we only have the following possibilities : $$x+1=0,\pm1, \pm2^k\Rightarrow x=-1,0,-2,-1\pm2^k.$$ However, we have $x\not=-1, x\not=0, x\not=-2$, because $x$ has to be a square of an integer (and $x\not=0$). So, we have $$x=-1\pm2^k.$$ In the same argument, we have $$x^2=-1\pm2^l.$$ Note that $k,l\ge1\in\mathbb Z.$

Hence, we have $$(-1\pm2^k)^2=-1\pm2^l\iff 2^{2k}\mp2^k+2=\pm2^l\iff 2^{2k-1}\mp2^{k-1}+1=\pm2^{l^1}.$$ Now, if $k-1\ge1$ and $l-1\ge1$, then we know that the left hand side is odd, and the right hand side is even, which is a contradiction.

So, we have "$k=1$ or $l=1$".

This leads $x=\pm2^k-1=\pm2^1-1\Rightarrow x=1,-3\Rightarrow x=1.$ ($x^2$ has to be a square.) Also, this leads $x^2=\pm2^l-1=\pm2^l-1\Rightarrow x^2=1,-3\Rightarrow x=1.$

So, this case leads $(x,y)=(1,\pm 2).$

(2) The case that $x+1$ and $x^2+1$ are coprime.

In this case, we know any two of $x,x+1,x^2+1$ are coprime. So, this leads that each of $x, x+1,x^2+1$ has to be a square number of an integer. However, it is impossible that $x$ and $x+1$ are both square numbers except $x=0$. However, we suppose that $x\not=0$ at the top. Hence, this case has no solution.

Now we reach a conclusion that the solutions of the given equation is only the followings:

$$(x,y)=(0,0),(1,2),(1,-2).$$

-
How did you go from $\gcd(x+1,x^2+1)=2$ to the conclusion that $x=\pm 2^k$? Agree with your case 2. – Jyrki Lahtonen Jan 2 '14 at 12:16
@i totally agree with @Jyrki this is a big "jump" – Konstantinos Gaitanas Jan 2 '14 at 12:19
Oh, you are right... I need to check it... but I'm tired:) I'll edit or delete this answer later. sorry. – mathlove Jan 2 '14 at 12:19