Show that $2^{2^n}+5$ is divisible by $3$ for all $n \geq 1.$ This is part of a larger proof that I am trying to do, but this is a fact I'm trying to wrap my head around and prove. Based on a Sage program, I was able to deduce by pattern that $2^{2^n}+5$ is divisible by $3$ for all $n \geq 1.$ If you factor numbers of this form until $n=6$ on Sage, you get that a prime factor of all of them is $3.$ I tried proving this through induction, but I couldn't quite figure out how to make the argument for the inductive step. I know modular arithmetic is the way to go, but it isn't something we've studied yet in class! Thank you for your help.
 A: We observe that,
$$2^{2^n}+5\equiv 2\left(2^{2^n-1}+1\right)~~\text{(mod 3)}$$
and
$$2^{2^n-1}+1=(2+1)(2^{2^n-2}-2^{2^n-3}+2^{2^n-4}-\cdots+1)$$
This means, $2^{2^n}+5\equiv 0~~\text{(mod 3)}.$

But, you can also complete the proof using mathematical induction:
Let $2^n-1=2m-1$, where $m\in\mathbb Z^{+}$.  Then, we can prove the stronger result:
$$2^{2m-1}+1\equiv 0~~\text {(mod 3)},\thinspace \forall m\in\mathbb Z^{+}$$
If $m=1$, then the statement is correct.
Assuming that, the statement is also correct for $m=k~:$
$$2^{2k-1}+1=3n,\thinspace n\in\mathbb Z^{+}$$
Then for $m=k+1$, we have
$$\begin{align}2^{2k+1}+1
&=4(3n-1)+1\\
&=3(4n-1),\thinspace n\in\mathbb Z^{+}\end{align}$$
Then by induction, you are done.
A: $2^{2^n}+5 \equiv (-1)^{2^n}-1 \mod 3$.
If $n\ge1$, the exponent is even, and the expression becomes $1-1\equiv 0 \mod 3$.
A: It's easy to prove by induction that $2^m \equiv 1 \pmod 3$ if $m$ is even, because $4 \equiv 1 \pmod 3$ (establishing your base case) and $2^{2(k+1)}=4 \cdot 2^{2k} \equiv (\text{using your inductive hypothesis})~1 \cdot 1 \equiv 1 \pmod 3$.  (Also, $2^m \equiv 2 \pmod 3$ if $m$ is odd, but you don't need that.)  $2^n$ is always even for $n \geq 1$, so $2^{2^n}+5 \equiv 1+5 \equiv 0 \pmod 3$.
A: $$2^{2^{n+1}}+5=2^{2^n}\cdot (2^{2^n}+5)- (5\cdot (2^{2^n}-1))$$
Why this helps, is that $$2^{2^n}-1\equiv 2^{2^n}+5\pmod 3$$ so if either is a multiple of $3$ both are.  This means we'd have a difference of multiples of $3$ , which is then a multiple of $3$. So we have the induction hypothesis proved. We now need a base case. $n=1$ produces $$2^{2^1}+5=2^2+5=4+5=9$$ which is an obvious multiple of $3$, so we are done.
