Proof for $\forall n\in \mathbb{N}: 7\mid(1 + 2^{2^n} + 2^{2^{n+1}})$

Question

I am stuck at the following exercise:

Prove that $\forall n\in \mathbb{N}: 7\mid(1 + 2^{2^n} + 2^{2^{n+1}})$.

I tried to prove the Expression by induction but I cannot find a way to prove the implication $$7\mid(1 + 2^{2^n} + 2^{2^{n+1}}) \Rightarrow 7\mid(1 + 2^{2^{n+1}} + 2^{2^{(n+1)+1}}).$$ Any help would be appreciated very much.

Answer 1

Let $a_n=2^{2^n}$. We have $a_{n+1}=a_n^2$, hence the sequence $\{a_n\pmod{7}\}_{n\geq 0}$ is periodic from some point on. Let we compile a small table: $$ \begin{array}{|c|c|c|c|c|c|}\hline n & 0 & 1 & 2 & 3 & \ldots \\ \hline a_n\pmod{7} & 2 & 4 & 2 & 4 & \ldots\\ \hline\end{array}$$ By induction it is trivial that $a_n\equiv 2\pmod{7}$ if $n$ is even and $a_n\equiv 4\pmod{7}$ if $n$ is odd.
In any case, $$ 1+a_n+a_{n+1} \equiv 1+2+4 \equiv \color{red}{0}\pmod{7} $$ and that proves the claim.

Answer 2

Suppose $1+2^{2^n}+2^{2^{n+1}}=7k$ and set, for simplicity, $a=2^{2^n}$. Then $2^{2^{n+1}}=a^2$ and $2^{2^{n+2}}=a^4$. Then \begin{align} &1+2^{2^n}+2^{2^{n+1}}=1+a+a^2 \\[4px] &1+2^{2^{n+1}}+2^{2^{n+2}}=1+a^2+a^4 \end{align} Then $$ (1+a^2+a^4)-(1+a+a^2)=a^4-a=a(a-1)(a^2+a+1)=7ka(a-1) $$ so $$ 1+a^2+a^4=7k+7ka(a-1) $$

Answer 3

Induction will work here. Assume $1+2^{2^n} + 2^{2^{n+1}}$ is divisible by 7. Note that $2^{2^{n+2}} = 2^{2^n4} = 16^{2^n} = (14+2)^{2^n} = 14M+2^{2^n}$ for some integer $M$. Then $1+2^{2^{n+1}} + 2^{2^{n+2}} = 1+2^{2^{n+1}}+(14+2)^{2^n} = 1+2^{2^{n+1}} +2^{2^n}+14M$, which must be a multiple of 7, since the first three terms are from the induction hypothesis.

Answer 4

Notice $\ \ \overbrace{x^4\!+x^2\!+1}^{\large f_{\Large n+1}} =\, (x^2\!-x+1)\,\overbrace{ (x^2\!+x+1)}^{\large f_{\Large n}} \,\ $ hence $\ f_n\mid f_{n+1}$

therefore by induction: $\ f_0\mid f_n\ $ for all $\ n \ge 0\,\ $ (in your case $\,f_0 = 7)$

---

Remark $ $ We can discover the factorization in many ways, e.g. by completing the square (see comment below), or, more generally, by the method of simpler multiples as below

$$x^2+x+1\,\ {\rm divides}\!\!\!\!\overbrace{\color{#0a0}{x^{\rm\large 2+\color{#c00}3\:\!J}}+x^{\rm\large 1+\color{#c00}3\:\!K}+\color{#90f}{x^{\rm\large \color{#c00}3L^{\phantom{|}}\!}}}^{\textstyle {\rm e.g.}\ \ \color{#0a0}{x^2}\ +\,\ x^4\,\ +\,\ \color{#90f}1\ \ {\rm in\ OP}\, \ \ \ }\qquad\qquad\qquad$$

Answer 5

The roots of $x^2+x+1$ over $\mathbb{F}_7$ are $x=2$ and $x=4$. If $n$ is odd, then $2^n\equiv 2\pmod{3}$, so that $2^{2^n}=2^2=4$ in $\mathbb{F}_7$. If $n$ is even, then $2^n\equiv 1\pmod{3}$, so that $2^{2^n}=2^1=2$ in $\mathbb{F}_7$.