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?
 A: 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$.
A: Modular arithmetic does not work well with division. So you cannot say that $\frac{3^{29}}{12} = \frac{3^{28}}{4}$ above, and a collection of similar arguments means your attempt is incorrect.
For the answer, try to find ways to simplify your calculation. For example, note that $3^3 = 27 \equiv 3 \mod 12$, so $$3^{29} \equiv (3^{3})^9 \times 3^2 \equiv 3^9 \times 3^2 \equiv (3^{3})^{3} \times 3^2 \equiv 3^3 \times 3^2 \equiv 3 \times 3^2 \equiv 27 \equiv 3 \mod 12$$
Where I basically used the fact noted many times in a row. Alternately, you could have also said that $3^k$ alternates modulo $27$, and this comes down to the same noted fact.
A: $$3^2\equiv1\pmod4,3^{2n}=(3^2)^n\equiv1^n$$
$$3^{2n+1}\equiv3\pmod{4\cdot3}$$
