Fermat's little theorem, which states that, for any prime number p and any integer a, a to the power of p minus a is always a multiple of p; or, in modular arithmetic language:
You might have come across the proof of FLT considering the congruence of two sets mod p (which might be a theme for future article); though I am sure you would be interested to know about a proof involving just a necklace and some fun combinatorics!
Our aim is essentially demonstrating that:
which is true iff (if and only if) the previous formulation is true.
We start with a concrete case with p=7, from which the proof generalises easily.
Consider a necklace with 7 coloured beads, and 5 different colours:
We want to count the number of different necklaces we could make from these ingredients. The rule is that two necklaces are the same and only counted once if we can otain one from the other through rotation. They are not the same if we can only obtain one from the other through procedures involving reflection.
Labelling the beads 1 to 7, each bead can have 5 different colours. So there are a total of 5^7 configurations including repetitions.
Which ones have we counted for more than one time? It seems like all different configurations would have been counted 7 times, from the 7 identical rotations of each; however, there is one exception: If all the beads are of one colour, no matter how you rotate it the necklace will always look the same. So it is only counted once:
There are five necklaces which have identical beads of the same colour. All other compositions have seven rotations being counted.
Therefore, the number of different necklaces we can make is
Which must be an integer, because it is the number of necklaces.
Generalising the proof, we simply consider a necklace with p beads of a different colours and proceed with identical procedure as above, deducing that (a^p-a)/p must be an integer because it is the number of different necklaces we can make with these rules and ingredients.
It is obvious why a has to be an integer in this proof (because it is the number of colours). More notable is that this proof only works if p is a prime.
If p is not a prime, not all configurations (except those which have p identical-coloured beads) would be counted for p times. This is because some of its rotations can overlap with a period of n rotations, where n is a factor of p. For example, if p=6:
From each of picture 1 to 6, the necklace is rotated clockwise through 1 bead. One can see that 1 is identical to 4 with respect to the colour of each bead 1-6, 2 is identical to 5, and 3 is identical to 6. Therefore, this configuration is not counted 6 times but only 3 times, and our proof above does not work.
Comentarios