I have a kind of confusion dealing with modular arithmetic, specially regarding remainders. I am aware of Euler/Fermat theorem that says: if p is prime, then 2^(p-1) is congruent to 1 module p.
However, supose that p is not prime. How is the best approach to compute a remainder?. For example: how to compute a remainder of 3^2348 by 25?
Thanks...
You must use Euler's $\varphi$ function: for any $a$ prime to $25$, $a^{\varphi(25)}=a^{20}=1$. Hence $$3^{3248}=3^{3248\bmod20}=3^8=\Bigl(\bigl(3^2\bigr)^2\Bigr)^2=6^2=11\mod25.$$
$3^4\equiv6\pmod{25},3^8\equiv6^2\equiv11\implies3^{10}=3^8\cdot3^2\equiv11\cdot9\equiv-1$
As $3248=325\cdot10-2,3^{3248}\equiv(-1)^{325}\cdot3^{-2}\equiv-9^{-1}\equiv11$
