The number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors 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&gt;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}$$
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&gt;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.
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.