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.
 A: 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}$

A: 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.
A: 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.$$
A: 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}$
