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

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

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:

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,

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.

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

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

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

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
• Examples
  • Further examles of divisibility criteria
• Equivalence relations
• A real life story

Copyright © 1996-2009 Alexander Bogomolny