Euler’s Theorem only works if a and n are coprime.
There is also a theorem called Fermat’s Little Theorem, which is a special case derived from Euler’s Theorem.
Fermat’s Little Theorem works only when the base of the modulus is a prime number, so phi p is just equal to p – 1. Try it for yourself
