2
$\begingroup$

Why: to make modulo and power calculations easier !

I will take an example to show my thoughts on Fermats Little theorem , Assume we want to calculate $3^{31}( mod 7)$

We see that $7$ is prime therefore i directly know that $3^7 \equiv 3 \pmod 7$ and $a^{7-1} \equiv 1 \pmod 7$.

$3^{31} \pmod7 \equiv 3^{6}*3^{6}*3^{6}*3^{6}*3^{7} \pmod7 \equiv 1*1*1*1*3 \equiv 3 \pmod7 $

I will take another example to show my thoughts on Euler's theorem , Assume we want to calculate $3333^{4444}( mod 100)$

We see that $100$ is not a prime number, therefore we can use Euler's theorem !

We start by checking $GCD(3333,100)$ which is $1$ therefore $3333^{\varphi(100)}\equiv 1 (mod 100)$

We calculate $\varphi(10) = 4$ therefore we get $3333^{40} \equiv 1 (mod 100) $

And then we continue simplifying..

As i know, Euler's theorem is a generalization of fermats little theorem. so can can we use Euler's theorem instead of fermat little therom, when trying to calculate $a^x \pmod m$ where $m$ is a prime number?

A side question:

how would you calculate $3^{40} (mod 23) $?

i tried with FLT and got stuck at $3^{17} (mod 23)$, is it possible to simplify it a bit more ?

$\endgroup$
  • $\begingroup$ Note: the gcd of $(3333,4444)$ is $1111$, not $1$ but I'm not sure why you needed to check that. Maybe you meant to write "GCD$(3333,100)=1$"? $\endgroup$ – lulu Oct 28 '15 at 12:22
  • $\begingroup$ True, i edited the question :)! $\endgroup$ – humble24 Oct 28 '15 at 12:30
  • $\begingroup$ Since you know Euler's theorem is more general, why ask? $\endgroup$ – Jean-Claude Arbaut Oct 28 '15 at 12:35
  • $\begingroup$ for confirmation. $\endgroup$ – humble24 Oct 28 '15 at 12:51
  • $\begingroup$ Then, since $\varphi(m)=m-1$ when $m$ is prime, it follows immediately that Fermat's little theorem is a particular case of Euler's theorem. Thus, of course, you can always use Euler's theorem instead (they both give the same information when $m$ is prime). $\endgroup$ – Jean-Claude Arbaut Oct 28 '15 at 13:28
1
$\begingroup$

For $3^{17} \pmod{23}$, you could do

$$3^2\equiv9\pmod{23}$$ $$3^4\equiv81\equiv12\pmod{23}$$ $$3^8\equiv144\equiv6\pmod{23}$$ $$3^{16}\equiv36\equiv13\pmod{23}$$ $$3^{17}\equiv39\equiv16\pmod{23}$$

See Exponentiation by squaring and Modular exponentiation on Wikipedia.

$\endgroup$

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.