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:
“If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nations greatest strength, will tell their own story to the world.”
—Susan B. Anthony (18201906)
“But counting up to two
Is harder to do....”
—Philip Larkin (19221986)