Fermat's Little Theorem
p is a prime, a be any integer, $a \not\equiv 0 \pmod{p}$
We have $a^{p-1} \equiv 1 \pmod{p}$
# Example
$3^{2018} \pmod{17} = 3^{126*16+2}=3^2=9$
It is a special case for Euler phi
p is a prime, a be any integer, $a \not\equiv 0 \pmod{p}$
We have $a^{p-1} \equiv 1 \pmod{p}$
$3^{2018} \pmod{17} = 3^{126*16+2}=3^2=9$
It is a special case for Euler phi