Prove that $4^n+ 1$ is not divisible by $3$ For all integers $n \ge 0$, prove that the value $4^n + 1$ is not divisible by 3.
I need to use Proof by Induction to solve this problem. The base case is obviously 0, so I solved $4^0 + 1 = 2$. 2 is not divisible by 3.
I just need help proving the inductive step. I was trying to use proof by contradiction by saying that $4^n + 1 = 4m - 1$ for some integer $m$ and then disproving it. But I'd rather use proof by induction to solve this question. Thanks so much.

Hint: Suppose $3$ does not divide $4^{n}+1$ for some $n\in\{0,1,\ldots\}$.
If $3$ divides $4^{n+1}+1$,
$$
0\equiv4^{n+1}+1\equiv4^{n}4+1\equiv \text{ } ?\text{ (mod }3\text{)}.
$$
(I have left out a step which you should fill in to arrive at a contradiction)
