<s>[INST] Proving $4^{47}\equiv 4\pmod{12}$ I know this is a simple exercise, but I was wondering if I can make the following logical jump in my proof:
We see that $4\equiv 4\pmod{12}$ and $4^2\equiv 4\pmod{12}$. Then we can recursively multiply by $4$ to get $4^{47}\equiv 4\pmod{12}$.
 [/INST] $4^{47}$ and $4$ are divisible by $4$ thus $4^{47}-4$ is a multiple of $4$.
Also, since $4 \equiv 1 \pmod{3}$ we have $4^{46}\equiv 1^{46}\pmod{3}$ and then
$$4^{47} \equiv 4 \pmod 3 \,.$$
Thus  $4^{47}-4$ is a multiple of $3$ and $4$, and hence of 12...
</s>