Fermat's Little Theorem

It comes from observation of multiplication tables modulo prime number p that all rows are nothing but a permutation of the first row {1, 2,... , p-1}. The same is true for the columns. Here I wish to verify that this is indeed so. The proof depends on the Euclid's Proposition VII.30

If two numbers, multiplied by one another make some number, and any prime number measures the product, then it also measures one of the original numbers.

Let a be one of the positive remainders of division by p: 0 < a < p. I wish to prove that [a]_p, [2a]_p, [3a]_p, ..., [(p-1)a]_p are all different. Which, in terms of remainders, claims that in the sequence {a, 2a, 3a, ..., (p-1)a} no two numbers are congruent modulo p. Assume the opposite: let there be two numbers 1 ≤ m < n < p such that na = ma (mod p). This would imply that p|a(n-m). By the Proposition VII.30 either p|a or p|(n-m). But both a and (n-m) are positive integers less than p. So it can't divide either of them. Contradiction.

It indeed follows that the set {[a]_p, [2a]_p, [3a]_p, ..., [(p-1)a]_p} is just a permutation of the set

{[1]_p, [2]_p, [3]_p, ..., [p-1]_p},

or that rows in the multiplication tables are just permutations of the first row.

If two sets are permutations of each other, then products of their elements are clearly equal:

[(p-1)!]_p	= [1]_p·[2]_p·[3]_p·...·[p-1]_p
	= [a]_p·[2a]_p·[3a]_p·...·[a(p-1)]_p
	= [a^p-1(p-1)!]_p
	= [a^p-1]_p·[(p-1)!]_p

Now, dividing by [(p - 1)!]_p (which is not 0 by Euclid's Proposition VII.30) gives 1 = [a^p-1]_p. Or, in terms of remainders,

a^p-1 = 1 (mod p)

Going over the proof we may notice that it's an overkill to require a to be less than p. The proof remains valid for any a not divisible by p.

The statement first appeared without proof in a letter dated October 18, 1640 that Fermat wrote to Frenicle de Bessy . The first proof was given by Leibniz (1646-1716) and the one above was found by Ivory in 1806. Euler proved the theorem in 1736 and its generalization in 1760. The theorem is now known as the Fermat's Little Theorem to distinguish it from the Fermat's Last or Great Theorem. The latter has been finally established by the Princeton mathematician Andrew Wiles (with assistance from Richard Taylor) in 1994.

Remark

The set {{[0]_N, [1]_N, [2]_N, ..., [p-1]_N} is an additive group. The set {[1]_p, [2]_p, [3]_p, ..., [p-1]_p} is a multiplicative group. For the latter we saw that to every element [a]_p in the group, there corresponds a permutation

{[a]_p, [2a]_p, [3a]_p, ..., [(p-1)a]_p}

of its elements. This relation is a group isomorphism: it preserves the group operation and is 1-1. A general statement, known as the Cayley's Theorem, asserts that this is a rule:

Every group is isomorphic to a group of permutations.

References

J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
U. Dudley, Elementary Number Theory, Dover, 2008
H.Davenport, The Higher Arithmetic, Harper&Brothers, NY
R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
P.Hilton, D.Holton, J.Pederson, Mathematical Reflections, Springer Verlag, 1997
Oystein Ore, Number Theory and Its History, Dover Publications, 1976

72372025