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

-

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:

1. T. Andreescu and D. Andrica, $360$ Problems for Mathematical Contests, GIL, 2003.
2. R. Gelca and T. Andreescu, Putnam and Beyond, Springer, 2007.
-
Thank you very much! – user140619 Apr 7 '14 at 12:10
Thank you for the references too! – user140619 Apr 7 '14 at 12:13
You're welcome. – user139587 Apr 7 '14 at 12:14

HINT:

If $x=5^{5^n}, 5^{5^{n+1}}=(5^{5^n})^5=x^5$

-
Thank you very much! – user140619 Apr 7 '14 at 12:09
@user140619, My Pleasure. From the link, we can say that $$x^{3m+2}+x^{3n+1}+x^{3p}$$ is composite as it is divisible by $$x^2+x+1$$ where $m,n,p$ are non-negative integers – lab bhattacharjee Apr 7 '14 at 15:08
@user140619, Unless $$m=n=p=0$$ – lab bhattacharjee Apr 7 '14 at 16:14

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

-

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.

-