17
$\begingroup$

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.

2 Answers 2

26

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

  • 1
    For the asker: this and similar factorizations may be found by evaluating polynomials at roots of unity.2012-12-25
  • 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$2012-12-25
  • 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$.2012-12-25
  • 0
    Thanks. But, how might one go about using roots of unity? It seems crazy to factor that so easily2012-12-25
  • 1
    @Alex: Here was my thinking (roughly): It looks a lot like the polynomial $x^2+x+1$, except the first term is different. This gives at least a few ideas to try. Perhaps multiply by $x-1$, or use some symmetry from the number $3$. The main term is different by an $x^3$ term, so both roots of $x^2+x+1$ have to divide $x^5+x+1$, and from here we get the factorization.2012-12-25
  • 2
    In fact, $x^{3k+2} + x + 1$ is divisible by $x^2 + x + 1$ for all nonnegative integers $k$.2012-12-25
  • 2
    According to PARI, $x^n + x + 1$ is irreducible for $1 < n < 300$ when $n \not\equiv 2 \bmod 3$.2012-12-25
  • 0
    @KCd: Interestingly, it turns out that $x^n+x+1$ is always irreducible for $n>1$, $n\not \equiv 2 \pmod{3}.$ See [this question](http://math.stackexchange.com/questions/264853/irreducibility-of-xnx1) and the paper which the accepted answer links to.2012-12-25
  • 0
    @EricNaslund: I knew about that paper of Selmer, but I had remembered only that it treated $x^n-x-1$, not also $x^n+x+1$.2012-12-25
  • 0
    I'm not following something... isn't $x=5^{5^{n}}$ imply that $x^5 =5^{5^{5n}}$? How would that equal $5^{5^{n+1}} = 5^{5^{n}} * 5^{5}$?2012-12-26
  • 0
    @Chubbycantorset: Recall that $$(a^b)^c=a^{bc}$$ so that $$\left(5^{5^n}\right)^5=5^{5^n\cdot 5}=5^{5^{n+1}}.$$2012-12-26
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$?

  • 1
    Curiously, this also works for other primes, e.g. 181.2012-12-26
  • 0
    Yes, it seems 31, 181 and 1741 divide all $a_n$, $n>0$. And 151 and 3301 divide $a_n$ for $n>1$.2012-12-26