EWD740 - 0

A short proof of one of Fermat's theorems.

Consider the np distinct "words" of p "characters" that can be formed from an "alphabet" of n distinct characters. Draw from each word an arrow to the word that is obtained by rotating its characters over one place to the left, i.e. from n0, n1, ..., np-1 an arrow is drawn to n1, ..., np-1, n0 . Because p successive rotations transform a word into itself, the arrows form cycles of lengths that are divisors of p.

Hence, if p is prime, 1 and p are the only possible cycle lengths. Because a cycle of length 1 corresponds to a word all characters of which are equal, exactly n distinct words occur in a cycle of length 1. Hence the remaining np-n words occur in cycles of length p, i.e. for any n and any prime p, np-n is a multiple of p.

Plataanstraat 5
The Netherlands
27 May 1980
prof.dr. Edsger W. Dijkstra
Burroughs Research Fellow

Transcription by John C Gordon

Last revised on Mon, 30 Jun 2003.