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