How can I prove that a number of the form $2^{2n}-1$ is divisible by 3?

Question

How can I prove that for each positive integer $n$ the number $2^{2n}-1$ is divisible by $3$? $3$?

Answer 1

You can use induction on $n$. Define $a_n = 2^{2n}-1$. Then for $n = 1$, we have $3|a_1 = 3$. Now suppose, inductively, $n \ge 2$ and the argument holds for all $n$. Then, for $n+1$, we have $$a_{n+1} = 2^{2n+2}-1 = 4 \cdot 2^{2n}-1 = 3\cdot2^{2n}+(2^{2n}-1) = 3\cdot2^{2n}+a_n$$ Now, by inductive hyphothesis, we have $3|a_n$ and obviously $3|3 \cdot 2^{2n}$. Therefore, we have $3|a_{n+1}$. So by induction, argument holds for all $n$.

Answer 2

Let $u_n:=4^n-1$ so $u_0=0$ while $u_{n+1}=4u_n+3$. Then $3|u_n$ follows by induction.