number theory - 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 ?

Answer

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.