2
$\begingroup$

I recently took a test that asked me to determine the value of $3^{82} \mod 5$.

I was unable to figure out how to do it on the test, but when I got home I noticed that there is a pattern to the remainders of $3^n$,

  • $3^{1} \mod 5 = 3$
  • $3^{2} \mod 5 = 4$
  • $3^{3} \mod 5 = 2$
  • $3^{4} \mod 5 = 1$
  • $3^{5} \mod 5 = 3$
  • $3^{6} \mod 5 = 4$
  • $3^{7} \mod 5 = 2$
  • $3^{8} \mod 5 = 1$
  • $3^{9} \mod 5 = 3$

Is the best strategy to follow this pattern up to the $82^{\text{nd}}$ remainder (obviously in an intelligent way) or is there some much more obvious trick to this question that I missed?

1 Answers 1

3

As you have observed $$3^4 \equiv 1 \pmod 5$$ This means that $$3^{4k} \equiv 1 \pmod 5$$ Hence, $$3^{80} \equiv 1 \pmod 5 \implies 3^{82} \equiv 3^2 \pmod{5} = 4 \pmod 5$$ In general, $$3^{4k + r} \equiv 3^r \pmod{5}$$

  • 0
    Thank you for your answer. It's not entirely clear to me how $3^4 \mod 1 \equiv 1$ tells us that $3^{4k} \mod 1 \equiv 1$. Could you explain this step?2012-11-07
  • 0
    @crazedgremlin $\rm\: \color{#0A0}{3^4}\equiv\color{#C00} 1\:\Rightarrow\: 3^{4k} = (\color{#0A0}{3^4})^k\equiv \color{#C00}1^k\equiv 1\:$ by the [Congruence Product Rule.](http://math.stackexchange.com/a/5376/242) It is essential to learn the arithmetic of congruences, as opposed to less flexible mod operations.2012-11-07
  • 0
    Great, thank you very much!2012-11-07