1. Historical Background
Pierre de Fermat wrote his friend Frénicle de Bessy in 1640 stating that he had discovered that for prime moduli p, provided p did not divide a, but his proof was overlong, so he did not bother to include the details. One might wish that Fermat had been more generous in recording his notes both in this instance and that famous “margin too small to contain∙∙∙ (his proof of Fermat’s Last Theorem)”. Leibniz appears to have proved the theorem prior to 1683 without publishing it, and then Euler reprised Leibniz’ work in a published version. This result, christened Fermat’s Little Theorem by Kurt Hensel in 1913, is the basis for a convenient method for detecting primality, or more correctly, compositeness    . If p does not divide a and is not congruent to , then p must be composite. Modular arithmetic, particularly with the aid of a computer, makes short work of calculating the residues of high powers of a needed to check this condition. Unfortunately, the invalidity of the converse to Fermat’s Little Theorem (if with a and n coprime, then n is prime) forces it to be used in a probabilistic way for detecting primality. If for lots of different admissible choices of n, then it looks more and more like n is probably prime. But there are many a for which and yet n is composite. Such a are called “Fermat Liars” and the n that go with them are termed pseudoprimes to the base a. A pseudoprime to every base, and they do exist but are relatively rare, is called a Carmichael number. Carmichael numbers completely defeat the usefulness of the theorem as a primality test. There is certainly no shortage of simple proofs of Fermat’s Little Theorem. It may be proved with a straightforward induction on the base a to show that is divisible by p, or by using a modular arithmetic argument. We present a proof of this useful theorem from an intuitively appealing direc- tion based on coloring the vertices of regular polygons with prime numbers of sides.
2. Burnside’s Lemma 
If G is a group of permutations acting on a set S, then for a particular , the invariant set of is the collection of all elements of S that are fixed points of , i.e. . The orbit of some is the collection of elements obtained by letting every permutation in G act on that s. Intuitively, there is a broad inverse size relationship between orbits and invariant sets. If most elements are not moved by most permutations, invariant sets will be large and orbits will be small, but more numerous. In 1897, the British mathematician William Burnside published the result, with attribution to Frobenius  , that if G is a group of permutations acting on the finite set S, then the number of orbits
of S under G is given by , where is the size of the
invariant set of the permutation . Burnside’s Lemma is a direct conse- quence of the Orbit/Stabilizer Theorem    and was known at least as early as Cauchy, hence it is sometimes called “the lemma that is not Burnside’s”  . We will color the elements of S, specifically the vertices of a regular polygon with a prime number of sides, and adapt Burnside’s/Not Burnside’s Lemma to the problem of enumerating distinct colorings.
A coloring is a mapping from the finite set S of objects to be colored to the finite set P, consisting of the “pallette” of colors. This is just a fanciful way of thinking about the rather dry notion of an arbitrary function between two finite sets. Colorings had their origin in the effort to establish the Four-Color Theorem, and they pop up in many seemingly unrelated combinatorial settings   . If the group G of permutations shuffles the objects of S, then those permutations will likewise shuffle the possible colorings of S. So a given can be regarded as a mapping from the set of P-colorings of S back to itself. More mathematically, there is a group of induced maps that form an action on the set of colorings . Each gives rise to a companion mapping that determines what happens to the available colorings whenever the underlying objects in S are permuted by . It is clear that is a group with the same order as G.
Just as the elements of S can be put into equivalence classes on the basis of whether they are in the same orbit under the action of G or not, colorings can be put into equivalence classes depending on whether they are in the same orbit under the action of or not. Orbits of colorings are called patterns. Two colorings and are equivalent, or represent the same pattern, if there is a such that for all we have . For example, if , , and , then if the permutation , and are equivalent provided , , and . You can see that , and so forth. We would write to signify this situation.
If we have a symmetrical object with a coloring, we can apply Burnside’s Lemma to enumerate the number of distinct patterns possible for the object. Let us consider a regular p-gon, where p is prime, and color the vertices with a pallette consisting of a colors, where p does not divide a. We will admit the digon to handle the case . Now we are not going to tear or fold the polygon, so the only permutations of colorings allowed are going to be those induced by the rotation group of the polygon, namely the cyclic group . The invariant set of a particular induced by an element of this group is easy to characterize. The zero rotation has colorings fixed by it, namely the total number of possible paint jobs or mappings from the vertices to the pallette. Every non-zero element of carries each pure coloring (every vertex the same color) into itself, so there would be a such colorings fixed by the action of those rotations. But none of these non-zero rotations can carry a non-pure coloring back to itself due to the indivisibility of p. Burnside’s Lemma then gives us the total count of possible distinct patterns as
. Evidently this is a
positive integer, and since p does not divide a, it must divide . But this means , which is Fermat’s Little Theorem.
We have established Fermat’s Little Theorem by coloring the vertices of a regular polygon and then finding the patterns that are stable under various rotations of the polygon. When the number of vertices is prime, the set of such invariant patterns is necessarily limited. This process lends itself to intuitively satisfying visualization. Burnside’s Lemma then enumerates the relatively sparse number of invariant patterns and gives a formula that is equivalent to the modular expression of Fermat’s Little Theorem. An interesting further application of this idea would be to search for other number-theoretic results using colorings of more complicated geometric objects and more general pattern enumeration methods, for example Polya’s Counting Theorem.