2
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$
$\endgroup$
3
  • $\begingroup$ @BarryCipra Ops yes of course! Thanks, I fix! $\endgroup$ – user Mar 8 '18 at 21:53
  • $\begingroup$ You're welcome. Incidentally, your answer made me realize I had made a (nonfatal) sign error in my own answer. So thank you! $\endgroup$ – Barry Cipra Mar 8 '18 at 21:58
  • $\begingroup$ @BarryCipra That's good! You are welcome too! $\endgroup$ – user Mar 8 '18 at 21:59
2
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.