# Have i understood Fermat little theorem and Euler's theorem correctly?

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 ?

• 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$"? – lulu Oct 28 '15 at 12:22
• True, i edited the question :)! – humble24 Oct 28 '15 at 12:30
• Since you know Euler's theorem is more general, why ask? – Jean-Claude Arbaut Oct 28 '15 at 12:35
• for confirmation. – humble24 Oct 28 '15 at 12:51
• 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). – Jean-Claude Arbaut Oct 28 '15 at 13:28

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