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.

The statement is true for $n=0$. Now, let it be true for $n=k$. Also, if possible, let it be false for $n=k+1$. Then, $4^{k+1} \equiv -1 \pmod{3} \implies 4 \cdot 4^k \equiv -1 \pmod{3} \implies 4^k \equiv -4 \pmod{3} \equiv -1 \pmod{3}$ (since $4^{-1} \equiv 4 \pmod{3}$). So, $3 \mid 4^k+1$, a contradiction. Hence, it's true for $n=k+1$. Hence the proof. 
