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 source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (16861743)
“But counting up to two
Is harder to do....”
—Philip Larkin (19221986)