# Determining the remainder of a small integer n raised to a high power when divided by m

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?

-

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