How does one show that for $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.

Question

For $k \in \mathbb{Z_+},3\mid2^{2^k} +5$ and $7\mid2^{2^k} + 3, \forall \space k$ odd.

Firstly,

$k \geq 1$

I can see induction is the best idea:

Show for $k=1$:

$2^{2^1} + 5 = 9 , 2^{2^1} + 3 = 7$

Assume for $k = \mu$

so: $3\mid2^{2^\mu} + 5 , \space 7\mid2^{2^\mu} + 3$

Show for $\mu +2$

Now can anyone give me a hint to go from here? My problem is being able to show that $2^{2^{\mu+2}}$ is divisible by 3, I can't think of how to begin how to show this.

Answer 1

You have already shown that the base cases hold.

Assume $3\mid 2^{2^k}+5$. Then $2^{2^k}\equiv 1$ mod $3$. Hence: $$2^{2^{k+1}}=2^{2^k*2}=\left(2^{2^k}\right)^2\equiv 1 \text{ mod } 3$$ Hence $3\mid 2^{2^{k+1}}+5$.

In the same way:

Assume $7\mid 2^{2^{k}}+3$. Then $2^{2^{k}}\equiv 4$ mod $7$. Hence: $$2^{2^{k+2}}=\left(2^{2^k}\right)^4\equiv 4^4 \text{ mod } 7$$ And since $4^4=256=36*7+4$, we see that $256\equiv 4\text{ mod }7$. So $7\mid 2^{2^{k+2}}+3$.

Answer 2

Hint: What if you tried to prove that:

• $3\mid 2^\ell+5$ whenever $\ell$ is even, and
• $7\mid 2^\ell+3$ whenever $\ell\equiv2\pmod6$ (or whenever $\ell-2$ is divisible by six).

And then prove ...

---

If you follow this path the real question is, of course, how to know what you should try to prove? The answer is to look at the remainders of consequtive powers of $2$. You should see a repeating pattern. Take advantage of that.

Answer 3

Hint $\,\ $ Apply the following $ $ fixed point induction $ $ to $\ f(j)\, =\, 2^{\Large 2^{\Large 2j+1}}$

Lemma $\ $ If $\,f(j\!+\!1)\color{#c0f} = f(j)^4\,$ then $\ {\rm mod\ n}\!:\,\ \forall n\ge 1\!:\ f(n)\color{#0a0}\equiv f(1) \Leftarrow\!\Rightarrow f(1)^4\color{#c00}\equiv f(1)\,$

Proof $\quad\ (\Rightarrow)\quad f(1)^4\color{#c0f}\equiv f(2)\color{#0a0}\equiv f(1).\quad\ (\Leftarrow)\quad f(n+1) \equiv f(n)^4\overset{induct}\equiv f(1)^4\color{#c00}\equiv f(1)$

Remark $\ $ So the gist is: successive iterations stay constant iff the initial point is fixed.

Answer 4

We have $2^2\equiv 1\pmod 3$ now one notes that $$2^{2^k}=(2^2)^{2^{k-1}}\equiv 1\pmod 3$$ so $\forall k$ we have $$2^{2^k}+5\equiv 6\equiv 0\pmod 3$$

We also have $2^{2^2}\equiv 2\pmod 7$ this means $2^{2^k}\equiv 2^{2^{k-2}}\pmod 7$ So when $k$ is odd $2^{2^k}\equiv 2^2\pmod 7$ and therefore $2^{2^k}+3\equiv 0\pmod 7$