2

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.

Killercamin
  • 801
  • 4
  • 17
  • 39
  • 1
    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 08 '18 at 21:10
  • 2
    It seem very fast! Maybe we can solve also without $\phi$ but it is of course longer! – user Mar 08 '18 at 21:12
  • 2
    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. https://en.wikipedia.org/wiki/Exponentiation_by_squaring – Thomas Andrews Mar 08 '18 at 21:14
  • 2
    This is the fastest and most standard way possible. No need to explain something else. I would avoid the arrow notation though. – Rebellos Mar 08 '18 at 21:16
  • 1
    For the last step , I suggest $3^4=81\equiv -12\mod 31$ , so $3^8\equiv 144\equiv 20\mod 31$ – Peter Mar 08 '18 at 21:18

4 Answers4

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}$
user
  • 154,566
2

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.

Barry Cipra
  • 79,832
2

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

Bernard
  • 175,478
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}$

TheWanderer
  • 5,126