# Prove that for any nonnegative integer n the number $5^{5^{n+1}} + 5^{5 ^n} + 1$ is not prime

My math teacher gave us problems to work on proofs, but this problem has been driving me crazy. I tried to factor or find patterns in the numbers and all I can come up with is that for $n > 0$, the number $\mod 100$ is $51$ but that does not help. There is definitely an easy way to do this but I can't think of it. Thanks if you can help

Prove that for any nonnegative integer $n$ the number $5^{5^{n+1}} + 5^{5^n} + 1$ is not prime.

-

Letting $x=5^{5^{n}},$ we have that $$5^{5^{n+1}}+5^{5^{n}}+1=x^{5}+x+1.$$ Now the claim follows since $$x^{5}+x+1=\left(x^{2}+x+1\right)\left(x^{3}-x^{2}+1\right).$$

Added: This may be of interest to the reader. This problem, along with KCd's comment, motivated the following question, asking whether or not $$x^n+x+1$$ is irreducible when $n\not\equiv 2\pmod{3}$, and $n\geq 1$. Alex Jordan's answer there referred to a paper of Ernst Selmer which proves that this polynomial is indeed irreducible for these $n$.

-
For the asker: this and similar factorizations may be found by evaluating polynomials at roots of unity. – Potato Dec 25 '12 at 1:28
Also note that strictly speaking, we need to mention the fact that both terms in the product are greater than $1$. This is easy to see since $x\geq 5$ – Eric Naslund Dec 25 '12 at 1:33
To elaborate on Potato's comment: in general, if $f$ vanishes where $g$ vanishes (and with at least the same multiplicity), $f$ is divisible by $g$. In this case, $x^5+x+1$ vanishes on $\omega, \overline{\omega}$ where $\omega = e^{\frac{2\pi i}{3}} = \frac{-1+i\sqrt{3}}{2}$, the 2 primitive roots of unity of order 3. Thus the polynomial $\phi_2(x) = (x-\omega)(x-\overline{\omega})=x^2+x+1$ must divide $x^5+x+1$. – Ofir Dec 25 '12 at 1:36
In fact, $x^{3k+2} + x + 1$ is divisible by $x^2 + x + 1$ for all nonnegative integers $k$. – Robert Israel Dec 25 '12 at 1:53
According to PARI, $x^n + x + 1$ is irreducible for $1 < n < 300$ when $n \not\equiv 2 \bmod 3$. – KCd Dec 25 '12 at 3:31

Here's a hint.

Let $a_n=5^{5^{n+1}}+5^{5^n}+1$.

Then, with some software, we can find that the smallest prime factor of $a_1$ and $a_2$ (at least...) is 31.

Can you show that 31 always divides $a_n$?

-
Curiously, this also works for other primes, e.g. 181. – Douglas S. Stones Dec 26 '12 at 11:04
Yes, it seems 31, 181 and 1741 divide all $a_n$, $n>0$. And 151 and 3301 divide $a_n$ for $n>1$. – Matthew Conroy Dec 26 '12 at 21:56