Does $3$ divide $2^{2n}-1$? Prove or find a counter example of : $3$ divide $2^{2n}-1$ for all $n\in\mathbb N$.
I compute $2^{2n}-1$ until $n=5$ and it looks to work, but how can I prove this ? I tried by contradiction, but impossible to conclude. Any idea ?
 A: A direct proof: $$2^{2n}-1=(2^n)^2-1=(2^n+1)(2^n-1).$$ Since $2^n$ is not divisible by 3, then either $(2^n+1)$ or $(2^n-1)$ must be divisible by 3.
A: Since $2^{2n}=4^n$, you get $$2^{2n}\equiv 1\pmod 3\implies 2^{2n}-1\equiv 0\pmod 3,$$
what prove the claim.
A: HINT: $$2^{2n}-1=4^n-1\equiv 1^n-1=1-1\equiv 0\mod 3$$
A: You can use the binomial theorem:
$$2^{2n}-1 = 4^n -1 = (3+1)^n -1 $$
$$= \left(3^n + {n \choose 1}3^{n-1} + {n\choose 2} 3^{n-2} + \cdots +{n\choose n-1}3 + 1 \right)-1.$$
When you cancel the last $-1$ with the $+1$, everything left has a factor of $3.$
Or, if you want induction, note that 
$$2^{2(n+1)}-1 = 4(2^{2n}) -1 = 4(2^{2n}-1) +4 -1 = 4(\mbox{multiple of 3}) +3. $$
A: Induction proof. Assume $2^{2n}-1$ is divisible by $3$.
Then $$\begin{align}2^{2(n+1)}-1&=2^2\cdot 2^{2n}-1\\
&=4\cdot (2^{2n}-1)+4-1\\
&=4(2^{2n}-1)-3
\end{align}$$
Since $2^{2n}-1$ is divisible by $3$, we get that $2^{2(n+1)}-1$ is divisible by $3$.

If you know linear recurrences, you can see that if 
$$a_n=2^{2n}-1$$
then you can show that $$a_{n+1}=5a_{n}-4a_{n-1}$$
So if you show that $a_0$ and $a_1$ are divisible by $3$, then all $a_n$ are divisible by $3$.
