<s>[INST] Prove by induction: $9\mid (4^{3n} + 8)$ for all integers $n \geq 0$. I cannot seem to figure this one out.
My though process so far is the following:
$\textit{Proof}$: For the base case n = 0, we have $9 \mid (4^0 + 8)$. This is true.
$\textit{Inductive step:}$ Suppose for $k \geq 0$ we have that $9\mid (4^{3k} + 8)$. We will show that $9 \mid (4^{3(k + 1)} + 8)$. The statement $9 \mid (4^{3k} + 8)$ can be expressed as $4^{3k} + 8 = 9a$ for integer $a$. Observe that
$$\begin{equation}\begin{split} 4^{3(k + 1)} + 8 &= 4^{3k}4^3 + 8 \\ &= 
 \dots \\ &\vdots \\ &= 9 (z)\end{split}\end{equation}$$
Where $z$ is some integer. I feel I am forgetting some algebraic properties or a manipulation of the equation above of some sort to help in this prove.
Any help is great! Thanks!
 [/INST] Well, we need to use $4^{3k} +8$ is divisible by $9$.
SO we have somehow isolate $4^{3k} + 8$ from $4^{3k}4^3 + 8$.
Only way I see to do that is $4^{3k}4^3 + 8= (4^3 - 1)4^{3k} + \color{blue}{(4^{3k} + 8)}$
Now we know $9$ divides $\color{blue}{(4^{3k} + 8)}$ so it suffices to show $9$ divides $(4^3-1)4^{3k}$ as well.
As the only prime factors of $4^{3k}$ is $2$ at suffices to show $9$ divides $4^3-1$.
And that's a single constant value.

  Oh... come on! Did you really need to peek at the spoiler to figure out how to prove $9$ divides into $4^3 -1$?

</s>