Simplify $3^{2018}\pmod{31}$

Question

I need to simplify $3^{2018}\pmod{31}$.

I just want to make sure I did this correctly.

$\phi(31)=30$ ,so $\frac{2018}{30}= 67$ remainder $8.$

Then $ \equiv3^{67\cdot30+8} \rightarrow \equiv (3^{30})^{67}\cdot3^8$ And $3^{30}\equiv 1\pmod{31.}$ Thus $(1)^{67}\cdot 3^8 \rightarrow \equiv 20 \pmod {31.}$ Is there a faster way or different approach for large modulus?

edit: yeah i just realized this is the fastest method, I was just concern that $3^{30} \equiv 1 \bmod 31$, since I was relying on my notes for this computation.

Answer 1

This is the faster way, since you reduce your exponent to a number less than 31. You must only to check the value of $3^8$, but note that $3^3=27 \equiv -4 \pmod{31}$. So $3^8 \equiv 144 \equiv 20 \pmod{31}$

Answer 2

It seems the faster way, as longer way also without $\phi$ or FLT note that we can obtain

• $3^5=243\equiv -5 \pmod{31}$
• $(-5)^3=-125\equiv -1 \pmod{31}$
• $3^{2018}=3^{2015}3^3\equiv(-5)^{403}(-4)\equiv(-5)(-4)=20\pmod{31}$

Answer 3

Not faster, but different, in that it gets there without knowing about Fermat's little theorem:

$$3^3=27\equiv-4\mod31$$ hence $$3^9\equiv-64\equiv-2\mod31$$ hence $$3^{45}\equiv-32\equiv-1\mod31$$ Now $$2018=1800+218=1800+180+38=45\cdot44+38$$ so $$3^{2018}\equiv3^{38}=(3^9)^4\cdot3^2\equiv(-2)^4\cdot9=144\equiv20\mod31$$

Remark: What makes this work as smoothly as it does is that a relatively small power of $3$ leaves a small residue ($-4$), a relatively small power of that residue leaves another small residue ($-2$), and a relatively small power of that residue gives residue $-1$. You can't always count of that happening, but sometimes you get lucky.

Answer 4

With the fast exponentiation algorithm: $$3^{2018}\equiv 3^{2018\bmod 30}\bmod31=3^8=\Bigl(\bigl((3^2)\bigr)^2\Bigr)^2=(81)^2\equiv (-12)^2=144\equiv 20\mod 31.$$