Advanced book on Mathematics Olympiad

5.2 Arithmetic 261

Fermat’s little theorem.Letpbe a prime number, andna positive integer. Then

np−n≡ 0 (modp).

Proof.We give a geometric proof. Consider the setMof all possible colorings of the
vertices of a regularp-gon byncolors (see Figure 36). This set hasnpelements. The
groupZpacts on this set by rotations of angles^2 kπp,k= 0 , 1 ,...,p−1.

Figure 36
Consider the quotient spaceM/Zpobtained by identifying colorings that become the
same through a rotation. We want to count the number of elements ofM/Zp. For that
we need to understand the orbits of the action of the group, i.e., the equivalence classes
of rotations under this identification.
The orbit of a monochromatic coloring has just one element: the coloring itself.
There arensuch orbits.
What if the coloring is not monochromatic? We claim that in this case its orbit has
exactlypelements. Here is the place where the fact thatpis prime comes into play.
The additive groupZpof residues modulopis generated byanyof its nonzero elements.
Hence if the coloring coincided with itself under a rotation of angle 2kπ/pfor some
0 <k<p, then it would coincide with itself under multiples of this rotation, hence
under all rotations inZp. But this is not possible, unless the coloring is monochromatic.
This proves that rotations produce distinct colorings, so the orbit haspelements. We
deduce that the remainingnp−nelements ofMare grouped in (disjoint) equivalence
classes each containingpelements. The counting of orbits gives

|M/Zp|=n+

np−n

p

,

which shows that(np−n)/pmust be an integer. The theorem is proved. 

In particular, ifnandpare coprime, thennp−^1 −1 is divisible byp. However, this
result alone cannot be used as a primality test forp. For example, L. Euler found that 341
divides 2^340 −1, while 341= 31 ×11. So the converse of Fermat’s little theorem fails.
We illustrate the use of Fermat’s little theorem with a short-listed problem from the
46th International Mathematical Olympiad, 2005.