Math Is Fun Forum

Kurre

Member

Registered: 2006-07-18

Posts: 280

Combinatorial proof of fermats little theorem

This is from the book "problem solving strategies" by Arthur Engel:

We have pearls with a colors. From these we make necklaces with exactly p pearls. First we make a string of pearls and there are a^p different strings. If we throw away the a one-colored strings a^p-a strings will remain. We connect the ends of each string to get necklaces. We find that two strings that differ only by a cyclic permutation result in indistinguishable necklaces, but there are p cyclic permutations of p pearls on a string. Hence the number of distinct necklaces is (a^p-a)/p. But this number must be an integer, thus p | a^p-a. q.e.d.

I find this proof pretty elegant, but I cant see how the proof uses that p must be a prime number? It seems that this proof shows that p | a^p-a for all natural p, but this isnt true. What am I missing?

Kurre

Member

Registered: 2006-07-18

Posts: 280

Re: Combinatorial proof of fermats little theorem

Ah, nevermind, I got it, if p wasnt prime then there are some necklaces where patterns of colored pearls can repeat, and thus doesnt have p different cyclic permutations.