<s>[INST] Find the remainder when $3^{29}$ is divided by $12$. 
Find the remainder when $3^{29}$ is divided by $12$. 
  a) $2$ ; b) $3$ ; c) $7$ ; d) $9$ ; e) $12$

Since $\dfrac{3^{29}}{12} = \dfrac{3^{28}}{4} = \dfrac{9^{14}}{4}$, and $9 \equiv 1 \mod 4$, I thought I could do $9^{14} \equiv 1^{14} \mod 4$, so that the answer is $1$. However, that is not one of the answer choices... Where did I go wrong?
 [/INST] Notice that we have


*

*$3^1 \equiv 3 \mod 12$

*$3^2 \equiv 9 \mod 12$

*$3^3 \equiv 3 \mod 12$

*$3^4 \equiv 9 \mod 12$

*...
So it goes like in this pattern. In general we have


*

*$3^{2k} \equiv 9 \mod 12,\ \ k > 0$

*$3^{2k+1} \equiv 3 \mod 12,\ \ k > 0$
And since $29$ is an odd number, the answer should be $3$.
</s>