Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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? –  crazedgremlin Nov 7 '12 at 1:07
    
@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. It is essential to learn the arithmetic of congruences, as opposed to less flexible mod operations. –  Bill Dubuque Nov 7 '12 at 1:23
    
Great, thank you very much! –  crazedgremlin Nov 7 '12 at 2:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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