For any $a \in \mathbb{N}$, $4^a \equiv (3a+1) \mod 9$

Question

For any $a \in \mathbb{N}$, $4^a \equiv (3a+1) \mod 9$. How do I prove this?

I have attempted to do so by induction(which I think should be sufficient).

For the base case: $4^0 = 1 \equiv (3(0)+1) \mod 9$.

I have tried assuming the inductive hypothesis $4^a \equiv (3a+1) \mod 9$ to try and get the result to be true for say $a+1$ but I can't get past that point and don't know whether this is the correct route. Any help would be appreciated.

Answer 1

Hint:

Note that $$4^a = (3+1)^a = 1+ \binom{a}{1}3 + \binom{a}{2}3^2 + \cdots +3^a=1+3a +9 \left(\binom{a}{2}+ \binom{a}{3}3+\cdots + 3^{a-2} \right)$$

If you insist on induction the induction step can be performed as follows: \begin{eqnarray*} 4^{a+1} & \equiv_9 & 4\cdot 4^a \\ & \equiv_9 & (3+1)\cdot (3a+1) \\ & \equiv_9 & 3\cdot (3a+1) + 3a+1 \\ & \equiv_9 & 9a+3 + 3a+1 \\ & \equiv_9 & 3(a+1) +1 \\ \end{eqnarray*}