<s>[INST] Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction.
I ran into the above problem. The base case $n=1$ gives $21$ which is divisible by $7$.
Now assume it is true for $n$. Then for $n+1$, we have the expression
$$ 1 + 2^{(2^{n+1})} + 2^{(2^{n+2})}$$
which is equal to
$$1 + 2^{(2^n\cdot 2)} + 2^{(2^n \cdot 2^2)}$$
but I do not really see how it helps.
Any ideas?
 [/INST] Consider the polynomial
$$f(x) = 1+x^{2^n} + \left(x^{2^{n}} \right)^2$$
We claim that $f(x) = (1+x+x^2)g(x)$, where $g(x)$ is also a polynomial for all $k \in \mathbb{Z}^+$. This is easy to prove, since $\omega = e^{2\pi i/3}$ and $\omega^2 = e^{4\pi i/3}$ are roots of $1+x+x^2$. We have $1+\omega^{2^n} + \left(\omega^{2^n}\right)^2 = 0$. Hence, $1+x+x^2$ divides $1+x^{2^n} + x^{2^{n+1}}$. Taking $x=2$, we obtain what you want.
</s>