Elegant Proof: Fermat Little Theorem

Let’s construct a necklace with p (p being prime) beads chosen from 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 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 ∎
Advertisements

One thought on “Elegant Proof: Fermat Little Theorem

  1. Pingback: Our Daily Story #1 : The Fermat’s Last Theorem | Math Online Tom Circle

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s