Proving that $2^{2^n} + 5$ is always composite by working modulo 3

Question

By working modulo 3, prove that $2^{2^n} + 5$ is always composite for every positive integer n.

No need for a formal proof by induction, just the basic idea will be great.

Answer 1

Obviously $2^2 \equiv 1 \pmod 3$.

If you take the above congruence to the power of $k$ you get $$(2^2)^k=2^{2k} \equiv 1^k=1 \pmod 3$$ which means that $2$ raised to any even power is congruent to $1$ modulo $3$.

What can you say about $2^{2k}+5$ then modulo 3?

It is good to keep in mind that you can take powers of congruences, multiply them and add them together.

---

If you have finished the above, you have shown that $3\mid 2^{2k}+5$. Does this imply that $2^{2k}+5$ is composite?

Answer 2

$2^(2n) +5$ is the same as $4^{n} +5 =(3+1)^n +5$
If you expanded the $(3+1)^n$ part , every term would be divisible by $3$ (except the last term $1$) The entire expression would be of the form $(3m +1) +5 = 3m +6$ which is divisible by $3$.

Answer 3

In order to work out this problem, we start by noticing $2^2\equiv 1 ~~~(\text{mod } 3)$.

What this means is $2^2$ (which is $4$) is $1$ greater than some multiple of $3$ (that multiple, in this case is obviously, $3$)

So if $2^2\equiv 1 ~~~(\text{mod } 3)~~\implies (2^2)^n\equiv (1)^n ~~~(\text{mod } 3)\implies 2^{2n}\equiv 1~~(\text{mod } 3)$,
Again, this means that any even power of $2$ is $1$ greater than some multiple of $3$.

So if $2^{2n}$ is $1$ greater than some multiple of $3$ (another way to say this is that $2^{2n}$ leaves a remainder of $1$ when divided by $3$), then what can you say about $2^{2n}+5$?.

To answer this, forget about $2^{2n}$ and just think about the remainder (i.e $1$). This is how modular arithmetic makes our live a lot easier. If $2^{2n}$ is $1$ greater than some multiple of $3$, then $2^{2n}+5$ should be $1+5=6$ greater than that multiple of $3$, right? But you know that $6$ is, by itself, a multiple of $3$. So, this should mean that $3|2^{2n}+5$.

A more formal (and a neat) argument could be:
$3|2^{2n}-1\implies 3|2^{2n}+5$, since $2^{2n}+5=(2^{2n}-1+6)$

Now since it has been shown that $2^{2n}+5$ is infact a multiple of $3$, it should be apparent that $2^{2n}+5$ is after all, composite.

I Hope it helps!

Answer 4

Hint: Rewrite the base using the fact that $2\equiv -1 \bmod 3$.

Answer 5

The basic idea is, work modulo 3. What happens, modulo 3, when you raise 2 to an even power?