1
$\begingroup$

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...

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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 $$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$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$.

$\endgroup$
0
$\begingroup$
  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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.