Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 1 down vote accepted

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.
share|improve this answer
    
Thank you very much! –  user140619 Apr 7 at 12:10
    
Thank you for the references too! –  user140619 Apr 7 at 12:13
    
You're welcome. –  Nick Apr 7 at 12:14

HINT:

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

Use Factorizing polynomial $x^5+x+1$

share|improve this answer
    
Thank you very much! –  user140619 Apr 7 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 at 15:08
    
@user140619, Unless $$m=n=p=0$$ –  lab bhattacharjee Apr 7 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.$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.