1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ $3$ and $12$ are multiples of $3$, $1$ isn't. And anyway, $1$ isn't even an option.... $\endgroup$ – Lord Shark the Unknown Feb 28 '18 at 3:53
  • $\begingroup$ And also, the question asks about the remainder modulo $12$, not modulo $4$. $\endgroup$ – Lord Shark the Unknown Feb 28 '18 at 3:54
  • 1
    $\begingroup$ Hint: $\,3^2 = 9 \equiv -3 \pmod{12}\,$. $\endgroup$ – dxiv Feb 28 '18 at 4:01
  • $\begingroup$ $1/4=3/12{}{}$. $\endgroup$ – Lord Shark the Unknown Feb 28 '18 at 4:10
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.