Proofs of Fermat's Little Theorem - Proof By Counting Necklaces

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 pa strings can be arranged into groups, each group containing exactly p strings. It follows that a pa is divisible by p.

Read more about this topic:  Proofs Of Fermat's Little Theorem

Famous quotes containing the words proof and/or counting:

    War is a beastly business, it is true, but one proof we are human is our ability to learn, even from it, how better to exist.
    M.F.K. Fisher (1908–1992)

    Is it not manifest that our academic institutions should have a wider scope; that they should not be timid and keep the ruts of the last generation, but that wise men thinking for themselves and heartily seeking the good of mankind, and counting the cost of innovation, should dare to arouse the young to a just and heroic life; that the moral nature should be addressed in the school-room, and children should be treated as the high-born candidates of truth and virtue?
    Ralph Waldo Emerson (1803–1882)