2

I have to show, using induction, that $2^{4^n}+5$ is divisible by $21$. It is supposed to be a standard exercise, but no matter what I try, I get to a point where I have to use two more inductions.

For example, here is one of the things I tried:

Assuming that $21 |2^{4^k}+5$, we have to show that $21 |2^{4^{k+1}}+5$.

Now, $2^{4^{k+1}}+5=2^{4\cdot 4^k}+5=2^{4^k+3\cdot 4^k}+5=2^{4^k}2^{3\cdot 4^k}+5=2^{4^k}2^{3\cdot 4^k}+5+5\cdot 2^{3\cdot 4^k}-5\cdot 2^{3\cdot 4^k}=2^{3\cdot 4^k}(2^{4^k}+5)+5(1-2^{3\cdot 4^k})$.

At this point, the only way out (as I see it) is to prove (using another induction) that $21|5(1-2^{3\cdot 4^k})$. But when I do that, I get another term of this sort, and another induction.

I also tried proving separately that $3 |2^{4^k}+5$ and $7 |2^{4^k}+5$. The former is OK, but the latter is again a double induction.

Is there an easier way of doing this?

Thank you!

EDIT

By an "easier way" I still mean a way using induction, but only once (or at most twice). Maybe add and subtract something different than what I did?...

Just to put it all in a context: a daughter of a friend got this exercise in her very first HW assignment, after a lecture about induction which included only the most basic examples. I tried helping her, but I can't think of a solution suitable for this stage of the course. That's why I thought that there should be a trick I am missing...

Ludolila
  • 3,034

5 Answers5

1

Note that $2^3 = 1\mod 7$ and hence $2^{3n} = 1 \mod 7$. Now, $4^k -1 = 0\mod 3$ and it follows that $2^{4^k-1} = 1\mod 7$ and $2^{4^k} = 2\mod 7$, Thus $$2^{4^k}+ 5 = 0 \mod 7 $$

1

Is there an easier way of doing this?

Note that $2^{4^{k+1}}=(2^{4^k})^4$.

Inductive step :

Supposing that $2^{4^k}+5=21m$ gives $$\begin{align}2^{4^{k+1}}+5&=(2^{4^k})^4+5\\&=(21m-5)^4+5\\&=\sum_{i=0}^{4}\binom{4}{i}(21m)^i(-5)^{4-i}+5\\&\equiv (-5)^{4}+5\quad\pmod{21}\\&\equiv 0\pmod{21}\end{align}$$

Added :

If you want to use neither the binomial theorem nor mod, then supposing that $2^{4^k}+5=21m$ gives $$\begin{align}2^{4^{k+1}}+5&=(2^{4^k})^4+5\\&=(21m-5)^4+5\\&=21(9261m^4-8820m^3+3150m^2-500m+30)\end{align}$$ So, $2^{4^{k+1}}+5$ is divisible by $21$.

mathlove
  • 139,939
1

You may have to use a few tricks here. The base case is clear.

Note that $2^{(4^n)} - 2^{(4^{n-1})} = 2^{(4^{n-1})}(2^{(3 \cdot 4^{n-1})} -1)$

So we have to prove that $2^{3 \cdot 4^{n-1}} - 1$ is a multiple of $21$. To do this, note that for $n \geq 2$,we can use modular arithmetic: since $3 \cdot 4^{n-1}$ is even, $3$ divides $(2^{3 \cdot 4^{n-1}} - 1)$ by Fermat's theorem. Similarly, since $3 \cdot 4^{n-1}$ is also a multiple of $6$, again by Fermat's theorem, $7$ divides $2^{3 \cdot 4^{n-1}} - 1$. Hence, $21$ divides it also.

Now, note that $2^{(4^n)} + 5 = 2^{(4^{n-1})} + 5 + (2^{(4^n)} - 2^{(4^{n-1})})$, hence assuming induction hypothesis, we have the result.

Sarvesh Ravichandran Iyer
  • 76,105
1

$2^{4^k}+5 \equiv (-1)^{4^k}+5 \equiv 1+5 \equiv 0 \pmod 3$

Proof by induction that $2^{4^k}+5 \equiv 0 \pmod 7$ for all non negative ingeters $k$.

If $k=0$, then $2^{4^k}+5 \equiv 2+5 \equiv 0 \pmod 7$

Suppose that $2^{4^m}+5 \equiv 0$ for some non negative integer $m$.

Then $2^{4^{m+1}}+5 \equiv 2^{4\cdot 4^m}+5 \equiv (2^4)^{4^m}+5 \equiv 16^{4^m}+5 \equiv 2^{4^m}+5 \equiv 0 \pmod 7$

Hence, by mathematical induction $2^{4^k}+5 \equiv 0 \pmod 7$ for all non negative integers $k$.

It follows that $2^{4^k}+5 \equiv 0 \pmod{21}$ for all non negative integers $k$.

Steven Alexis Gregory
  • 26,769
0

  1. $2^{4^1} \equiv -5 \bmod 21$

  2. $2^{4^{n+1}} = 2^{4^n \cdot 4} = (2^{4^n})^4 \equiv (-5)^4 = 625 \equiv -5 \bmod 21$

Denis Korzhenkov
  • 755