# Can this divisibility be proven in general?

Let $$n$$ be a positive integer with $$n\equiv 4\mod 6$$ and define $$p:=\frac{n^2+n+1}{3}$$ (which is in this case a positive integer as well).

Conjecture : $$p^2\mid n^n+(n+1)^{n+1}$$ for every $$n$$ of the given form.

The conjecture is true upto $$n=10^9$$

Trial : We have to show $$(n^2+n+1)^2 \mid 9(n^n+(n+1)^{n+1})$$ and with $$x^6\equiv (x+1)^6\equiv 1\mod (x^2+x+1)$$ I could show $$x^2+x+1\mid x^n+(x+1)^{n+1}$$ , but I did not manage to find the general remainder of $$9(x^n+(x+1)^{n+1})$$ modulo $$(x^2+x+1)^2$$ to finish the proof. Can "lifting the exponent" help here ?

• Does it help that $n^2+n+1\mid n^3-1$? Mar 26 at 12:31
• For small $n$, I have $\color{red}3p^2\mid n^n+(n+1)^{n+1}$. I can neither prove it nor find a counterexample. Apr 1 at 8:32

Proposition. Let $$n\equiv 5\pmod 6$$, then $$\left(\frac{n^2-n+1}{3}\right)^2\text{ divides }n^n+(n-1)^{n-1}.\tag{*}$$
Proof. This follows the proof strategy of Proposition 4.3 in the cited paper. We set $$m=\varepsilon=1$$, $$\varepsilon'=-1$$ to show that $$|\operatorname{Disc}(x^n+x-1)|=n^n+(n-1)^{n-1}$$ and $$x^n+x-1=(x^2-x+1)h(x)$$.
This proposition aligns with your statement by shifting $$n\mapsto n+1$$.
Note: An even stronger assertion noted by @mathlove in the comments can be derived using the same approach. Just note that Lemma 2.1 implies a stronger divisibility: $$\operatorname{Disc}(x^2-x+1)\operatorname{Res}(x^2-x+1,h(x))^2 \text{ divides } |\operatorname{Disc}(x^n+x-1)|.$$ Now just apply $$\operatorname{Disc}(x^2-x+1)=-3$$.