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

Question

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.

Answer 1

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$.

Answer 2

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$?