Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

I am confused as to how to solve this question.

For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds

My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a positive integer

So, $2^{2k} -1 = 3m$

$2^{2k} = 3m+1$

after this, I'm not quite sure where to go. Can anyone provide any hints?

Hint: If $2^{2k} - 1$ is divisible by $3$, then write

\begin{align*} 2^{2(k + 1)} - 1 &= 2^{2k + 2} - 1 \\ &= 4 \cdot 2^{2k} - 1 \\ &= 4 \cdot \Big(2^{2k} - 1\Big) + 3 \end{align*}

Do you see how to finish it up?

This technique is motivated by attempting to shoehorn in the term $2^{2k} - 1$, since that's the only piece we really know anything meaningful about.

Note that $$\sum_{k=0}^{n-1} 4^k={4^n-1\over4-1}$$ is an integer.

If we rewrite $2^{2k}-1$ in binary, we get the number $$2^{2k}-1=\underset{\text{$2k$-times}}{\underbrace{111111\dots11}}$$ consisting of $2k$ ones. (I.e., there are $k$ pairs of them.)

If this is not clear immediately, just notice that by adding one to the above number we get $$2^{2k}=1\underset{\text{$2k$-times}}{\underbrace{000000\dots00}}.$$

Now we can simply notice that this number can be obtained as the sum (written in binary) $$ \begin{align*} 110000\dots00&+\\ 1100\dots00&+\\ \dots&+\\ 11&=\\ 111111\dots11& \end{align*} $$ where each summand is multiple of $3=(11)_2$.