Why does the diophantine equation $x^2+x+1=7^y$ have no integer solutions?

Solution 1:

Continuing from @Batominovski's answer,

the problem asks us to find all the values taking $\pm 1$ in the three following recurrent linear sequences satisfying $a_n = 5a_{n-1} - 7a_{n-2}$,

• $1,2,3,1,-16,-87,-323,\ldots$
• $0,1,5,18,55,149,360,\ldots$
• $1,3,8,19,39,62,37,\ldots$

Looking at the recurrence relation mod $18$, we have $a_n \equiv 5a_{n-1}+11a_{n-2} \equiv 5(5a_{n-2}+11a_{n-3}) + 11a_{n-2} \equiv a_{n-3}$.

Looking at the first three terms of each sequence modulo $18$, we can already discard $2/3$ of all the terms and also remove the possibility of a $-1$ appearing, which reduces the problem to finding the $1$ values in the linear recurrent sequences satisfying $a_n = 20a_{n-1}-343_{n-2}$

• $1,1,-323,-6803,\ldots$
• $1,55,757,-3725,\ldots$
• $1,19,37,-5777,\ldots$

Now each sequence is a linear combination of the coefficient sequences of $(2-\omega)^{3n} = (1-18\omega)^n = (10 - 9 \sqrt{-3})^n$, that is, the two sequences

• $1,10,-143,-6290,\ldots$
• $0,-9,-180,-513, \ldots$

(with integer coefficents in all three cases)

With the binomial theorem, we can expand $(1+9(1-\sqrt{-3}))^n = 1 + 9(1-\sqrt{-3})n + 81(1-\sqrt{-3})^2n(n-1)/2 + \ldots$.

If we place ourselves in $\Bbb Z_3[\sqrt{-3}]$ and we notice that $v_3(9^k/k!) >= 3k/2 \to \infty$, we can reorder the summation and get $1 + [9(1-\sqrt{-3}) + O(81)]n + O(81)n^2 + \ldots$ i.e. each coefficient sequence can be extended as a function $\Bbb Z_3 \mapsto \Bbb Z_3$ which is a power series in $n$ with coefficients in $\Bbb Z_3$

Now, if a power series is of the form $a_0 + a_1 n + a_2n^2$ with $|a_1| > |a_2|,|a_3|,|a_4|,\ldots$, then it is a bijection from $\Bbb Z_3$ to $a_0+a_1\Bbb Z_3$.

The $a_1$ coefficients modulo $81$ in our three sequences are $9-9=0, 9-9 \times (-5) = 54 \neq 0, 9-9 \times (-1) = 18 \neq 0$.

In the last two cases we deduce that the sequence is injective so the initial occurence of $1$ is the only one.

As for the first sequence, we have that both $a_1$ and $a_2$ are of the order of $3^4$. But then its derivative is of the right form to show that it has a single zero at some $n_0 \in \Bbb Z_3$. By setting $m = n-n_0$, we get a new power series of the form $b_0 + b_2m^2 + b_3m^3 + \ldots$ where $|b_2| > |b_3|,|b_4|,\ldots$. This shows that the power series is $2$-to-$1$ (with the exception of $0 \mapsto b_0$), so the two values of $1$ we already know are the only ones.

Solution 2:

Sketch of My Idea:

Let $\omega:=\frac{-1+\sqrt{-3}}{2}$ and $\bar{\omega}:=\frac{-1-\sqrt{-3}}{2}$. Then, $7=(2-\omega)(2-\bar{\omega})$. Hence, $$(x-\omega)(x-\bar{\omega})=x^2+x+1=7^y=(2-\omega)^y(2-\bar{\omega})^y\,.$$ Since $7\nmid x-\omega$, we may assume without loss of generality that $x-\omega=u(2-\omega)^y$, where $u$ is a unit (i.e., $\pm1$, $\pm\omega$, and $\pm\bar{\omega}$). Then, $x-\bar{\omega}=\bar{u}(2-\bar{\omega})^y$, where $\bar{u}$ is the complex conjugate of $u$. Thus, $$-1=\frac{u(2-\omega)^y-\bar{u}(2-\bar{\omega})^y}{\omega-\bar{\omega}}\,.$$

Now, define $a_n(u)$ to be $\frac{u(2-\omega)^n-\bar{u}(2-\bar{\omega})^n}{\omega-\bar{\omega}}$ for $n\in\mathbb{Z}$. You have that $a_n(u)=5a_{n-1}(u)-7a_{n-2}(u)$ for all $n\in\mathbb{Z}$. Then, investigate each $u$. You should find that, only for $n=0$, $n=1$, or $n=3$, there exists a unit $u$ such that $a_{n}(u)=-1$. Now, since $a_n(-u)=-a_n(u)$, you may only look for solutions to $a_n(u)=\pm 1$ with $u \in \{1,\omega,\bar{\omega}\}$.

Solution 3:

A sketch of my thoughts:

Let $\nu_7(n)=\max\{m\in\mathbb{N}:7^m\mid n\}$. A good idea may be to prove that if $\nu_7(x^2+x+1)=\nu_7(x^3-1)-\nu_7(x-1)=y>3$ then $x$ has to be large, say $x\geq 7^{y-1}$. In such a case, however, $x^2+x+1$ is too big to be just $7^y$ and it must have some other prime factor.

By this way, the problem boils down to finding (or, at least, lower-bounding) the two elements of order three in $G=\left(\mathbb{Z}_{/(7^y\mathbb{Z})}\right)^*$, that is a cyclic group with $o(G)=6\cdot 7^{y-1}$.

If $y=1$, that elements are $2$ and $4$. If $y=2$, that elements are $18$ and $30$. If $y=3$, that elements are $18$ and $18^2$. In general, we may compute such elements by solving $z^2+3\equiv 0\pmod{7^y}$. If $y=4$, such elements are $1047$ and $1353$. If $y=5$, such elements are $1353$ and $15453$.

We just need to find a pattern, or an alternative reason for which $4\cdot 7^y-3$ cannot be a square for $y>3$. Obviously if $y$ is even $4\cdot 7^y-3$ is too close to a square to be a square itself, so we may assume that $y$ is odd.