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.

I think that if you need to use induction, instead of proving "$4^n+1$ is not divisible by $3$", you should prove the more specific "$4^n+1$ has remainder $2$ when divide by $3$".
$$4^n+1=3k+2\implies4^n=3k+1\implies4^{n+1}=12k+4$$
$$\implies4^{n+1}+1=12k+5\implies4^{n+1}+1=3(4k+1)+2$$
