# $4^{2^n}+2^{2^n}+1$ is Divisible by $7$

I have one question.

How do I prove that $$4^{2^n}+2^{2^n}+1$$ is Divisible by $7$ ? thanks in advances.

• Induction or modular arithmetic are two approaches that come to mind. Have you tried that? Nov 23, 2014 at 23:32

Note that $$(2^{2^n}-1)(4^{2^n}+2^{2^n}+1) = 8^{2^n}-1 \equiv 1-1 \equiv 0 \pmod 7.$$

Now $\text{ord}_7(2) = 3$ so $$7|2^{2^n}-1 \iff 3|2^n.$$

Thus, the result follows.

Consider $4^{2^n} + 2^{2^n} + 1 \bmod 7$. To understand $4^{2^n} \bmod 7$, notice that Fermat's Little Theorem informs us that $4^6 \equiv 1 \bmod 7$, and in particular that the exponent can be considered mod $6$.

How does $2^n \bmod 6$ behave? Starting at $0$, it looks like $1, 2, 4, 2, 4, \ldots$. There are only three cases: when $n = 0, 1, 2$. Everything else falls into these three residue classes.

So determining $4^{2^n} + 2^{2^n} + 1 \bmod 7$ reduces to understanding it for $n = 0, 1, 2$. These are all immediately checked.

Let $2^{2^n}=t_n$, then $t_n=t_{n-1}^2$. We want to show that $t^2_n+t_n+1$ is divisible by $7=4+2+1=t^2_0+t_0+1$. Now \begin{aligned}t_n^2+t_n+1&=(t_n+1)^2-t_n\\ &=(t_{n-1}^2+1)^2-t_{n-1}^2\\ &=(t_{n-1}^2+t_{n-1}+1)(t_{n-1}^2-t_{n-1}+1). \end{aligned} The result follows by reduction/induction.

for the part of $$2^{2^n}$$

$$2 ≡ 2 \pmod{7}$$

$$2^2 ≡ 4 \pmod{7}$$

$$2^3 ≡ 1 \pmod{7}$$

for the part of $$4^{2^n}$$

$$4 ≡ 4 \pmod{7}$$

$$4^2 ≡ 2 \pmod{7}$$

$$4^3 ≡ 1 \pmod{7}$$

so we need to discuss different situation according to $$2^n \pmod{3}$$

there are two situations:

$$2^n ≡ 2 \pmod{3}$$ if $$n=2k+1$$ for $$k=0,1,2,...$$

and

$$2^n ≡ 1 \pmod{3}$$ if $$n=2k$$ for $$k=0,1,2,...$$

so for $$n=2k+1$$,

$$4^{2^n}+2^{2^n}+1 ≡ 4^2 + 2^2 + 1 ≡ 21 ≡ 0 \mod{7}$$

for $$n=2k$$,

$$4^{2^n}+2^{2^n}+1 ≡ 4 + 2 + 1 ≡ 7 ≡ 0 \mod{7}$$

An induction would work:

Consider the case $n=0$. Then we have $4^{2^0}+2^{2^0}+1=7$ so the statement is true. Now suppose that it is true for $k\in\mathbb{N}_0$. For $k+1$ we have: $$4^{2^{k+1}}+2^{2^{k+1}}+1=4^{2\cdot 2^{k}}+2^{2\cdot 2^{k}}+1=16^{2^{k}}+4^{2^{k}}+1$$ Since $16≡2\pmod{7}\implies 16^{2^{k}}≡2^{2^{k}}\pmod7$: $$16^{2^{k}}+4^{2^{k}}+1≡2^{2^{k}}+4^{2^{k}}+1≡0 \pmod{7}$$ As supposed.