Divisor of $x^2+x+1$ can be square number?

Question

$$1^2+1+1=3$$ $$2^2+2+1=7$$ $$8^2+8+1=73$$ $$10^2+10+1=111=3\cdot37$$ There is no divisor which is square number. Is it just coincidence? Or can be proved?

*I'm not english user, so my grammer might be wrong

Answer 1

What about $x=653$, where $$x^2+x+1=427063=7\cdot (13\cdot 19)^2\,?$$ How did I find this $x$? I first suppose that $x^2+x+1=ay^2$ for some positive integers $a$ and $y$. This means $$(2x+1)^2-a(2y)^2=-3\,.$$ Let $u:=2x+1$ and $v:=2y$. Then, we are to solve the Pell-type equation $$u^2-av^2=-3\,,$$ where $u,v\in\mathbb{Z}_{>0}$. In particular, the case $x=2$ yields $a=7$ and $y=1$. Therefore, I attempt to solve $$u^2-7v^2=-3\,,\tag{*}$$ where a minimal solution is $(u,v)=(5,2)$. Since $u^2-7v^2=1$ has the minimal solution $(u,v)=(8,3)$, we obtain an infinite family of solutions $(u,v)$ of (*): $$u+v\sqrt{7}=(5+2\sqrt{7})\,(8+3\sqrt{7})^k\,,\tag{#}$$ where $k$ is a positive integer. We want $u$ to be odd, so $k=1$ does not work. With $k=2$, we get $(u,v)=(1307,494)$, so $$x=\frac{1307-1}{2}=653\text{ and }y=\frac{494}{2}=13\cdot 19$$ form a counterexample. (Using $k=-2$, we get lhf's counterexample $x=18$. Indeed, with even values of $k$ in $(\#)$, we obtain infinitely many counterexamples.)

Answer 2

No, for $x=18$ we get $x^2+x+1=343=7^3$.

Here are the first few counterexamples:

$$ \begin{array}{rrl} x & x^2+x+1 & \text{factorization}\\ 18 & 343 & 7^3 \\ 22 & 507 & 3 \cdot 13^2 \\ 30 & 931 & 7^2 \cdot 19 \\ 67 & 4557 & 3 \cdot 7^2 \cdot 31 \\ 68 & 4693 & 13 \cdot 19^2 \\ 79 & 6321 & 3 \cdot 7^2 \cdot 43 \\ 116 & 13573 & 7^2 \cdot 277 \\ 128 & 16513 & 7^2 \cdot 337 \\ 146 & 21463 & 13^2 \cdot 127 \\ 165 & 27391 & 7^2 \cdot 13 \cdot 43 \\ 177 & 31507 & 7^2 \cdot 643 \\ 191 & 36673 & 7 \cdot 13^2 \cdot 31 \\ 214 & 46011 & 3 \cdot 7^2 \cdot 313 \\ \end{array} $$

Answer 3

The square of any prime $p\equiv1\pmod3$ appears as a factor of $x^2+x+1$ for some choice of $x$.

This is seen as follows.

The multiplicative group $\Bbb{Z}_{p^2}^*$ of coprime residue classes modulo $p^2$ is known to be cyclic of order $p(p-1)$. It follows that there is an element of order three in that group. Let the residue class of $x$ be one such. Because $p>3$ the order of $x$ modulo $p$ is also equal to three. Implying that $x-1$ is not a multiple of $p$. But $$x^3-1=(x-1)(x^2+x+1)\equiv1-1=0\pmod{p^2}$$ by construction, so we can conclude that $$x^2+x+1\equiv0\pmod{p^2}.$$

---

A non-deterministic way of finding such an $x$ is to take a random integer $a$, and calculate the remainder $x$ of $a^{p(p-1)/3}$ modulo $p^2$. If the result is $x\neq1$, then we have found the required element of order three.

For example, with $p=31$, $a=3$ we find that $$ 3^{31(31-1)/3}=3^{310}\equiv521\pmod{31^2}. $$ And with $x=521$ we get $$ 521^2+521+1=271963=31^2\cdot283 $$ as promised.

---

On the other hand no prime $p\equiv-1\pmod3$ will appear as a factor of $x^2+x+1$ for any integer $x>1$. This is because the factorization $(x^3-1)=(x-1)(x^2+x+1)\equiv0\pmod p$ implies that $x$ has order $1$ or $3$ in the group $\Bbb{Z}_p^*$. In the former case $x\equiv1\pmod3$ and therefore $x^2+x+1\equiv1+1+1=3\not\equiv0\pmod p$. In the latter case Lagrange's theorem from elementary group theory tells us that $3$ must be a factor of the order of the group $G=\Bbb{Z}_p^*$. As $|G|=p-1$ we can conclude that $p\equiv1\pmod3$.

---

By more or less the same argument we can show that for all $p\equiv1\pmod3$ the number $x^2+x+1$ can be made divisible by any power $p^k$. This time the group has order $p^{k-1}(p-1)$. As an example consider $p=7,k=5$. The above method produces $$3^{7^4(7-1)/3}\equiv1353\pmod{7^5}.$$ And, predictably, $$1353^2+1353+1=7^5\cdot109.$$