Note that it is enough to prove
We will assume a to be relatively prime to p. This proof will make use of our base a multiplied by all the numbers from 1 to p-1. It turns out that if p is prime, the values 1a through (p-1)a (modulo p) are just the numbers from 1 through p-1 rearranged, a consequence of the following lemma. We then multiply all those numbers together, resulting in a formula from which the theorem follows.
Lemma: If a is relatively prime to p and x and y are integers such that xa = ya (mod p), then x = y (mod p).
Proof of lemma: xa = ya (mod p) means that p divides xa - ya = a (x - y). We know that a does not contain the prime factor p, so (x - y) must contain it, since the prime factorization is unique by the fundamental theorem of arithmetic. So p divides (x - y), which means x = y (mod p), which completes the proof of the lemma.
Proof of theorem:
Consider the set P = {1a, 2a, 3a, ... (p-1)a}. These numbers are different modulo p by the lemma, and none of them is zero modulo p (again by the lemma: 0a = ka (mod p) would imply 0 = k modulo p, but k is too small for that). So modulo p, the set P is the same as the set N = {1, 2, 3, ... (p-1)}. So if we multiply the elements of these two sets together, we will get the same result modulo p:
A direct proof
Regrouping the left side:
Now we would like to cancel the common term (p-1)factorial from both sides. This is allowed by the lemma, since p and (p-1)! can have no factor in common, again by the fundamental theorem of arithmetic. Dividing out (p-1)!, we get:
Here we use mathematical induction.
First, the theorem is true for a=1, then one proves that
that if it is true for a = k, it is also true for a = k + 1, concluding that the theorem is true for all a.
Before the main argument the following lemma is needed
Inductive proof with the binomial theorem
when p is prime. The Binomial theorem tells us that
is, by the fundamental theorem of arithmetic, a multiple of p, so the whole term is a multiple of p if 0 < i < p. This means the whole sum from i = 1 to i = p'\' - 1 equals 0 mod p. So, (a + b)p mod p indeed equals ap + bp mod p when p'' is prime.Back to the proof of the theorem. We proceed now with the two induction steps.
Here is an interesting proof which involves very little symbolic mumbo-jumbo.
Let us say that I make closed bracelets out of open chains that consist of p coloured links, with a choice of a different colours; and that I can use the links in any combination. Now, since these are closed bracelets, if I give you one, but you will be able to rotate it at will. So the 9-link bicolor bracelet ABAABBBBB is the same as BBABAABBB (you can rotate the bracelet), but it is different from BBBBBAABA (you cannot reverse it or recolour it).
Some 9-link bracelets can be made from only one "directional" open chain, such as AAAAAAAAA; however, some can be made from more than one such chain (ABBABBABB, BABBABBAB, BBABBABBA all make the same bracelet).
If you tell me how many links a bracelet is to have (call this number p), how many different bracelets of that size can I make, and out of how many distinct open chains can I make each one? Since it is Fermat's Little Theorem we are trying to prove, let us restrict ourselves to cases where p is prime. Let us find the answer thus:
Here we prove the special case a = 2 using the fixed points of a 1D-map which is commonly encountered in dynamical systems.
Define the "tent" map:
and consider the dynamical system xn+1 = f(xn), n = 0, 1, 2, ... If x0 is chosen in the interval [-1,1], then all xn will remain in that same interval.
The fixed points of f are -1 and 1/3.
If p is a prime number, then the p-iterated map fp has 2p fixed points which are solutions of:
So, we have 2p – 2 fixed points, forming disjoint orbits of period p. Then (2p – 2)/p is a natural number, the number of orbits of period p. So p' divides 2p'' - 2.
Take this into account: numerical calculations must fail for great p due to
rounding errors of the calculator or the computer.
Tn(x) = FP(nx), x<1
Tn(x) = 1, x=1
FP: Fractional Part
Lemma 1: Let n be an integer greater than 1. The function Tn(x) has
n fixed points in (0,1).
Lemma 2: Let a and b be positive integers. Then for all x belognig
to (0,1):
Ta(Tb(x)) = Tab(x)
Using values a and p, we consider the p-periodic point of Ta.
These p-periodic points are fixed points of Ta iterated p times, which
is Ta^p. This has a^p fixed points. Of these, exactly a are fixed
points of Ta.
Since p is prime the rest of them have minimal period p under Ta.
This means that there are a^p-a points that have minimal period p.
Since each point with minimal period p lies in an orbit p, there are
(a^p-a)/p orbits of size p. Since this is an integer, we see that p
divides (a^p-a).A second proof using Dynamical systems
For any n we define in the interval (0,1) ->(0,1) ( ) closed