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.

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.

share|improve this question
add comment

2 Answers

up vote 24 down vote accepted

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

share|improve this answer
1  
For the asker: this and similar factorizations may be found by evaluating polynomials at roots of unity. –  Potato Dec 25 '12 at 1:28
3  
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
2  
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
2  
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
2  
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
show 6 more comments

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

share|improve this answer
1  
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
add comment

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.