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?
Best Answer
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}$$