Find the least nonnegative residue of a number Find the least nonnegative residue of $4^{47} \bmod 12$. I began by having $4^2$ congruent to $4 \bmod 12$ but I am not sure where to go from there.

Since $4^2\equiv 4$ we\ have
$$
4^4\equiv 4 \mod 12 \\
4^8 \equiv 4 \mod 12 \\
4^{16}\equiv 4 \mod 12 \\
4^{32}\equiv 4 \mod 12 \\
4^{40}= 4^{32}\cdot 4^8 \equiv 4^2 \equiv 4 \mod 12 \\
4^{44}= 4^{40}\cdot 4^4 \equiv 4^2 \equiv 4 \mod 12 \\
4^{46}= 4^{44}\cdot 4^2 \equiv 4^2 \equiv 4 \mod 12 \\
4^{47}= 4^{46}\cdot 4^1 \equiv 4^2 \equiv 4 \mod 12 \\
$$
So the answer is $4$.
I used the binary expansion of $47$
$$
47=32+8+4+2+1$$
You can also use induction to show that $4^k \equiv 4 \mod 12$ for $k\ge 1$
