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
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
It indeed follows that the set
{[1]_{p}, [2]_{p}, [3]_{p}, ..., [p1]_{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:

Now, dividing by [(p  1)!]_{p} (which is not 0 by Euclid's Proposition VII.30) gives 1 = [a^{p1}]_{p}. Or, in terms of remainders,
a^{p1} = 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 (16461716) 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}, ..., [p1]_{N}} is an additive group. The set {[1]_{p}, [2]_{p}, [3]_{p}, ..., [p1]_{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}, ..., [(p1)a]_{p}} 
of its elements. This relation is a group isomorphism: it preserves the group operation and is 11. 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, SpringerVerlag, 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, AddisonWesley, 1994.
 P.Hilton, D.Holton, J.Pederson, Mathematical Reflections, Springer Verlag, 1997
 Oystein Ore, Number Theory and Its History, Dover Publications, 1976
 Modular Arithmetic
 Chinese Remainder Theorem
 Euclid's Algorithm
 Pick's Theorem
 Fermat's Little Theorem
 Wilson's Theorem
 Euler's Function
 Divisibility Criteria
 Examples
 Equivalence relations
 A real life story
Contact Front page Contents Algebra
Copyright © 19962018 Alexander Bogomolny
67404979