In Fermat's little theorem, if mod is not prime? Today I learned about Fermat's little theorem
It says -  

Fermat's little theorem states that if p is a prime number, then for
  any integer a, the number a p − a is an integer multiple of p. In the
  notation of modular arithmetic, this is expressed as $a^p \equiv a \mod p$ 

It considers "p" as a prime numbers. But what if "p" is not prime? Then if those cases how to solve this type of problems?
 A: There is a generalised form of Fermat, often known as the Fermat-Euler theorem.
Normally we write Fermat as $a^{p-1}\equiv 1 \mod p$
Then the generalised form is $a^{\phi(n)}\equiv 1 \mod n$ for $(a,n)=1$ i.e.  $a$ is coprime to $n$
$\phi(n)$ is known as the Euler Totient Function and counts the number of integers between $1$ and $n-1$ which are coprime to $n$. For a prime $p$ this is all $p-1$ of them. In the general case, various proofs including a version of inclusion-exclusion say that if $$n=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}$$ where the $p_i$ are the distinct prime divisors of $n$ then $$\phi(n)=n\left(1-\frac 1{p_1} \right) \left(1-\frac 1{p_2} \right)\dots \left(1-\frac 1{p_r} \right)$$
One way to see the generalised result is to note that the numbers having $0\lt r\lt n$ and $(r,n)=1$ form  group under multiplication $\mod n$ - it is easy to see that they include $1$ and they inherit associativity from the integers. They are closed under multiplication, and a counting argument shows that inverses must exist. $\phi(n)$ is the order of this group.
A: There is the Carmichael Theorem, which provides results stronger than Euler's Theorem, which generalizes Fermat's Little Theorem to non-prime modulo.
