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}$.
 A: The idea is absolutely correct. You just need to formalise it by using an inductive argument. I would try to prove that $4^n \equiv 4 \bmod 12$ for all $n$. This is a classic example of proof by induction.
Base Case
If $n=1$ then is $4^1 \equiv 4 \bmod 12$? Well, clearly $4^1 \equiv 4 \bmod 12$.
Induction Step
Assume that for $n=k$ we have $4^n \equiv 4 \bmod 12$, does this imply that $4^{n+1} \equiv 4 \bmod 12$?
Well, if $4^k \equiv 4 \bmod 12$ then $4^{k+1} = 4 \times 4^k \equiv 4 \times 4 \bmod 12 \equiv 4 \bmod 12$.
Conclusion
It follows that $4^n \equiv 4 \bmod 12$ for all $n \in \mathbb{Z}^+$.
A: $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...
A: $$4^{47}\equiv 4\pmod{12}$$
$$4^{47}-4=4 \cdot \left(4^{46}-1\right)=4 \cdot \left(4^{23}-1\right)\cdot \left(4^{23}+1\right)=$$
$$=4 \cdot \left(4-1\right)(4^{22}+4^{21}\cdot1+\ldots+1)\cdot \left(4^{23}+1\right)=4 \cdot3 \cdot \left(4^{22}+4^{21}\cdot1+\ldots+1\right)\cdot \left(4^{23}+1\right)=$$ $$=12 \cdot \left(4^{22}+4^{21}\cdot1+\ldots+1\right)\cdot \left(4^{23}+1\right)$$ 
which is divisible with $12$. 
