Let’s construct a necklace with p (p being prime) beads chosen from m distinct colors.
There will be m^p permutations of necklaces
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.
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 ∎
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)
m^(p-1) ≡ 1 (mod p) if p prime & (m, p) = 1 ∎