Elegant Proof: Fermat Little Theorem

Let’s construct a necklace with p (p being prime) beads chosen from m distinct colors.
There will be m^p permutations of necklaces
less:
1. m permutations of necklaces with beads of same color;
2. Joining the 2 ends of the necklace to form a loop. For prime p beads, there will be p cyclic permutations of beads which are the same.

Total distinct necklaces = (m^p – m) / p  …[*]
which is an integer, ie p divides (m^p – m)
m^p - m ≡ 0 (mod p)
or m^p  ≡ m (mod p) if p prime  ∎

From [*],  m.[m^(p-1) – 1] / p
If m and p are relatively prime, i.e. (m, p) = 1
then p divides (m^(p-1) – 1),
m^(p-1)  – 1≡ 0 (mod p)
or
m^(p-1) ≡ 1 (mod p)  if  p prime & (m, p) = 1 ∎