induction - Prove $4^{n} -1$ is divisible by $3$ for all $ngeq1$

I'm doing some homework and cant seem to get my head around this inductive proof.

So far I have got:

Atom case: $4^1 -1 = 3$, so proved for basic case.

Closure:

Assume $4^k - 1$ is divisible by $3$, Show that $4^{k+1} -1$ is divisible by $3$.

So: $4^k-1 = 4^k\cdot4 -1$ but this is where I get stuck, unsure where to go from here.

Any help much appreciated!

Thanks

Answer

Hint $ $ To induct multiply the first two congruences below (by the Congruence Product Rule)

$$\begin{align} \bmod 3\!:\quad\ \ 4&\equiv 1\\[.3em] 4^{\large n}&\equiv 1\ \ \ {\rm i.e.}\ \ P(n)\\ \overset{\rm multiply}\Longrightarrow\ 4^{\large n+1} &\equiv 1\ \ \ {\rm i.e.}\ \ P(n\!+\!1) \end{align}$$

Remark $\ $ The proof is a special case of the inductive proof of the Congruence Power Rule, which is the straightforward induction extension of the Product Rule.

If congruences are unfamiliar then you can instead use the Product Rule in Divisibility form:

$$\begin{align} {\rm mod}\,\ m\!:\, A\equiv a,\, B\equiv b&\ \ \,\Longrightarrow\,\ \ AB\equiv ab\qquad\text{Congruence Product Rule}\\[3pt] m\mid A-a,\ B-b&\,\Rightarrow\, m\mid AB-ab\qquad\text{Divisibility Product Rule}\\[4pt] {\bf Proof}\quad (A-a)B+a(B&-b)\, = AB-ab\end{align}$$

Then the original proof becomes $\,\ 3\,\mid\, \underbrace{4-1}_{\large A\,-\,a},\, \underbrace{4^n-1}_{\large B\,-\,b}\,\Rightarrow\, 3\,\mid\, \underbrace{4\cdot 4^{\large n}-1\cdot 1}_{\large AB\,-\,ab} = 4^{\large n+1}-1$