How do you find reminder of $m^{x}$ divided by $n$ using Euler's and Fermat's little theorem? Can anyone show me step-by-step how to apply Fermat's little theorem and Euler's theorem?
Example: What is the remainder of $59^{28}$ divided by $7$?
The following is the way I know how to do these types of problems:
$59^{28} = (56+3)^{28}$... since $7|56$ then we are left with
$3^{28} = 3^{2*2*7} = 3^{4*7} = 81^{7} = (77+4)^{7}$... since $7|77$ then we are left with
$4^{7} = 4^3*4^{4} = 64*4^{4} = (63+1)*4^{4}$... since $7|63$ then we are left with
$1*4^{4} = 4^4 = 4^3*4 = 64*4 = (63+1)*4$... since $7|63$ then we are left with 4
Since we are left with just 4, we can just do: $4\mod{7} = 4$
So the remainder is 4!
Applying Fermat's little theorem:
$$ \begin{align*} 7 \not\mid 59 &\implies 59^{6} \equiv 1 \pmod{7} \\ &\implies 59^{28} \equiv 59^{6(4) + 4} \equiv (59^6)^459^{4} \equiv 1^459^4 \equiv 59^4 \equiv 3^4\equiv 4\pmod{7} \end{align*} $$
Applying Euler's theorem: $$ \begin{align*} \gcd(59,7) = 1 &\implies 59^{6} \equiv 1 \pmod{7} \\ &\implies 59^{28} \equiv 59^{6(4) + 4} \equiv (59^6)^459^{4} \equiv 1^459^4 \equiv 59^4 \equiv 3^4\equiv 4\pmod{7} \end{align*} $$
The two theorems' applications are essentially the same here because Euler's theorem generalizes Fermat's little theorem from prime modulus to non-prime modulus. Since 7 is prime, Fermat's little theorem suffices.