The number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors

Question

Prove that the number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors, not necessarily distinct.

Doing what the hint has suggested, I have done the same where $n>1$, and took $\bmod 7$. I then found that $2^{2^n} + 2^{2^{n - 1}} + 1=7k$.

However, I got stuck when trying to simplify the case of $n=3$, since $$2^8+2^4+1=273=3\cdot 7\cdot 13$$

I do not understand where the 13 is from, since I thought that it would be something like $$2^{2^n} + 2^{2^{n - 1}} + 1 \equiv 0 \pmod {2^n-1}$$

Answer 1

For $n=3$ you have shown that $7$ is a factor and since $2^{2p} \equiv 1 \pmod 3$ you know $3$ is a factor. Since $2^8+2^4+1 \gt 21$ there is another. Now you have at least three prime factors. That settles $n=3$, but not higher $n$. You don't have to find $13$, you just need to show there is another factor.

Answer 2

We start with $x^4+x^2+1=\left(x^2+1\right)^2-x^2=\left(x^2-x+1\right)\left(x^2+x+1\right)$. Thus, we can proceed by induction (on $n$) that $2^{2^n}+2^{2^{n-1}}+1$ has at least $n$ prime factors. For $n=1$, there is nothing to prove. Suppose the statement is true for $n=k$ for some $k\in\mathbb{N}$. Then, for $n=k+1$, $$2^{2^{k+1}}+2^{2^k}+1=\left(2^{2^k}-2^{2^{k-1}}+1\right)\left(2^{2^k}+2^{2^{k-1}}+1\right)\,.$$ By the induction hypothesis, $2^{2^k}+2^{2^{k-1}}+1$ has $k$ prime factors. Furthermore, $2^{2^k}-2^{2^{k-1}}+1>1$ has at least one prime factor. Hence, $2^{2^{k+1}}+2^{2^k}+1$ has at least $k+1$ prime factors. We are done.

Answer 3

You could substitute $2^{2^{n-2}}$ for a letter, say $a$ and prove that $a^4+a^2+1$ is divisible by $a^2+a+1$ using polynomial long division. More info here: https://en.m.wikipedia.org/wiki/Polynomial_long_division

This way, you can prove that there is another factor added for every increase in an $n$ value.