Contest problem involving primes and factorization Prove that for any nonnegative integer $n$, the number
$$5^{5^{n+1}}+ 5^{5^{n}}+1$$
is not prime.
I want only some hints and the method to follow, but I don't need the full solution. Thanks.
 A: HINT:
If $x=5^{5^n}, 5^{5^{n+1}}=(5^{5^n})^5=x^5$
Use Factorizing polynomial $x^5+x+1$
A: Hint $\ \ f = x^2+x+1\,$ divides $\,x^{\rm\large 2+\color{#c00}3\,J}+x^{\rm\large 1+\color{#c00}3\,K}+x^{\rm\large \color{#c00}3L} = g,\,\ $ e.g. $\,\ g = x^5 + x + 1$
Proof $\ \ {\rm mod}\ f\!:\,\ 0\,\equiv\, (x\!-\!1)f\,\equiv\, x^{\large 3}-1\,\Rightarrow\,\color{#c00}{x^{\large 3}\equiv 1},\,$ therefore
$$\begin{eqnarray} g \! &&=\, x^{\large 2}\, (\color{#c00}{x^{\large 3}})^{\rm\large J}\! + x\,(\color{#c00}{x^{\large 3}})^{\rm\large K}\! + (\color{#c00}{x^{\large 3}})^{\rm\large L}\\ &&\equiv\, x^2\ \color{#c00}{(1)}\ \ +\ x\,\ \color{#c00}{(1)}\ \ +\ \ \color{#c00}{(1)}\\ &&\equiv\, f\equiv\, 0\end{eqnarray}\qquad$$
Remark $\ $ If modular arithmetic is unfamiliar you can proceed equivalently as follows
$$ g - f = x^2\color{#c00}{(x^{\rm\large 3J}-1)} + x\color{#c00}{(x^{\rm\large 3K}-1)} + \color{#c00}{(x^{\rm\large 3L}-1)}$$
By the Factor Theorem each $\,\rm\color{#c00}{red}\,$ term is divisible by $\,x^3-1\,$ so also by $\,f,\,$ by $\,x^3-1 = (x\!-\!1)f.$ Thus since $f$ divides the RHS it divides the LHS, i.e.  $\,f\mid g-f\,$ so $\,f\mid (g-f)+f = g.$
A: Substitute $x = 5^{5^{n}}$ in the factorisation
$$x^5+x+1=(x^2+x+1)(x^3-x^2+1)$$
to obtain a factorization of the number $5^{5^{n+1}}+ 5^{5^{n}}+1$. Then it should not be difficult for you to prove that both factors are greater than $1$.
References:


*

*T. Andreescu and D. Andrica, $360$ Problems for Mathematical Contests, GIL, 2003.

*R. Gelca and T. Andreescu, Putnam and Beyond, Springer, 2007.

A: There is a very easy method but you asked for a hint and I don't know how to tell you without giving the whole game away.
Let's try this: if you compute the expression for $n=0$ there is a very obvious prime factor $p$.  If you try it for $n=1$ the same prime is a factor.  If you now simplify $5^{5^k}$ modulo $p$ for $k=0,1,2,\ldots\,$, the problem is practically solved.
