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
    Great, thank you very much!2012-11-07