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

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.

• Isn't this fast enough ? The only problem remaining is how to calculate $3^8$ modulo $31$ as fast as possible. And the solution is correct, you applied Euler's theorem. – Peter Mar 8 '18 at 21:10
• It seem very fast! Maybe we can solve also without $\phi$ but it is of course longer! – user Mar 8 '18 at 21:12
• Not much easier, no. But note that you can compute $3^8$ with only three multiplications, modulo $31$. So once you've got the expression down to $a^n\bmod m$ where $0\leq n<\phi(m)$, you can use the method of repeated squaring to compute the value in $O(\log n)$ multiplications. en.wikipedia.org/wiki/Exponentiation_by_squaring – Thomas Andrews Mar 8 '18 at 21:14
• This is the fastest and most standard way possible. No need to explain something else. I would avoid the arrow notation though. – Rebellos Mar 8 '18 at 21:16
• For the last step , I suggest $3^4=81\equiv -12\mod 31$ , so $3^8\equiv 144\equiv 20\mod 31$ – Peter Mar 8 '18 at 21:18

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

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.

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}$
• @BarryCipra Ops yes of course! Thanks, I fix! – user Mar 8 '18 at 21:53
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.$$