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 p1. It turns out that if p is prime, the values 1a through (p1)a (modulo p) are just the numbers from 1 through p1 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, ... (p1)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, ... (p1)}. So if we multiply the elements of these two sets together, we will get the same result modulo p:
Regrouping the left side:
Now we would like to cancel the common term (p1)! from both sides. This is allowed by the lemma, since p and (p1)! can have no factor in common, again by the fundamental theorem of arithmetic. Dividing out (p1)!, we get:
Inductive proof with the binomial theorem
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
<math> ({}_{i}^{p}) </math> is, by the fundamental theorem of arithmetic, a multiple of p, so the whole term <math> ({}_{i}^{p}) a^{i} b^{pi} </math> 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 a^{p} + b^{p} 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 mumbojumbo.
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 9link 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 9link 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:
So what do we have? We have a unicolor bracelets, each from one unicolor open chain; and the other a^{p}a (multicolor) open chains make (a^{p}a)/p bracelets, each from p open chains. This shows that p divides (a^{p}a). Q. E. D.
A proof using dynamical systems
Here we prove the special case a = 2 using the fixed points of a 1Dmap which is commonly encountered in dynamical systems.
Define the "tent" map:
and consider the dynamical system x_{n+1} = f(x_{n}), n = 0, 1, 2, ... If x_{0} is chosen in the interval [1,1], then all x_{n} will remain in that same interval.
The fixed points of f are 1 and 1/3.
If p is a prime number, then the piterated map f^{p} has 2^{p} fixed points which are solutions of:
But two of these fixed points are –1 and 1/3. All the others must have period p, since any period would have to be divisor of p but the prime number p doesn't have any nontrivial divisors.
So, we have 2^{p} – 2 fixed points, forming disjoint orbits of period p. Then (2^{p} – 2)/p is a natural number, the number of orbits of period p. So p' divides 2^{}p  2. QED
Take this into account: numerical calculations must fail for great p due to rounding errors of the calculator or the computer.
A second proof using Dynamical systems
For any n we define in the interval (0,1) >(0,1) ( ) closed
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 pperiodic point of Ta. These pperiodic 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^pa points that have minimal period p. Since each point with minimal period p lies in an orbit p, there are (a^pa)/p orbits of size p. Since this is an integer, we see that p divides (a^pa).
This is similar to the direct proof. Trivially, the integers 1, ..., p1 form a group under multiplication mod p. This group is finite, so clearly the subgroup generated by any a in 1, ..., p1 must have size q where q divides the size of the original group, p1. That is, <math> a^{q} = 1 \mod p </math>. But since p1 = rq for some integer r, <math>a^{p1} = 1 \mod p</math>. Add the special case where a = p and we get the full proof.
Search Encyclopedia

Featured Article
