Find the remainder when $3^{29}$ is divided by $12$.

Question

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?

Answer 1

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$.

Answer 2

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.

Answer 3

$$3^2\equiv1\pmod4,3^{2n}=(3^2)^n\equiv1^n$$

$$3^{2n+1}\equiv3\pmod{4\cdot3}$$