Proof By Counting Necklaces
This is perhaps the simplest known proof, requiring the least mathematical background. It is an attractive example of a combinatorial proof (a proof that involves counting a collection of objects in two different ways).
The proof given here is an adaptation of Golomb's proof.
To keep things simple, let us assume that a is a positive integer. Consider all the possible strings of p symbols, using an alphabet with a different symbols. The total number of such strings is a p, since there are a possibilities for each of p positions (see rule of product).
For example, if p = 5 and a = 2, then we can use an alphabet with two symbols (say A and B), and there are 25 = 32 strings of length five:
- AAAAA, AAAAB, AAABA, AAABB, AABAA, AABAB, AABBA, AABBB,
- ABAAA, ABAAB, ABABA, ABABB, ABBAA, ABBAB, ABBBA, ABBBB,
- BAAAA, BAAAB, BAABA, BAABB, BABAA, BABAB, BABBA, BABBB,
- BBAAA, BBAAB, BBABA, BBABB, BBBAA, BBBAB, BBBBA, BBBBB.
We will argue below that if we remove the strings consisting of a single symbol from the list (in our example, AAAAA and BBBBB), the remaining a p − a strings can be arranged into groups, each group containing exactly p strings. It follows that a p − a is divisible by p.
Read more about this topic: Proofs Of Fermat's Little Theorem
Famous quotes containing the words proof and/or counting:
“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)
“But counting up to two
Is harder to do....”
—Philip Larkin (1922–1986)