Proving that $2^{2^n} + 5$ is always composite by working modulo $3$ 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. 
 A: The basic idea is, work modulo 3. What happens, modulo 3, when you raise 2 to an even power?
A: 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?
A: Hint: Rewrite the base using the fact that $2\equiv -1 \bmod 3$.
A: 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!
A: $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$.
