Proofs of Fermat's little theorem

This article collects together a variety of proofs of Fermat's little theorem, which states that for every prime number p and every integer a (see modular arithmetic).

The total number of such strings is ap since there are a possibilities for each of p positions (see rule of product).

Using the above rule, we can complete the proof of Fermat's little theorem quite easily, as follows.

[2] We start by considering a family of functions Tn(x), where n ≥ 2 is an integer, mapping the interval [0, 1] to itself by the formula where {y} denotes the fractional part of y.

For any positive integers n and m, and any 0 ≤ x ≤ 1, In other words, Tmn(x) is the composition of Tn(x) and Tm(x).

Now let us properly begin the proof of Fermat's little theorem, by studying the function Tap(x).

The main idea of the proof is now to split the set S up into its orbits under Ta.

This holds for every orbit of S. Therefore, the set S, which contains ap − a points, can be broken up into orbits, each containing p points, so ap − a is divisible by p. (This proof is essentially the same as the necklace-counting proof given above, simply viewed through a different lens: one may think of the interval [0, 1] as given by sequences of digits in base a (our distinction between 0 and 1 corresponding to the familiar distinction between representing integers as ending in ".0000..." and ".9999...").

The fixed points of this will be sequences that are cyclic with period dividing n. In particular, the fixed points of Tap can be thought of as the necklaces of length p, with Tan corresponding to rotation of such necklaces by n spots.

This proof could also be presented without distinguishing between 0 and 1, simply using the half-open interval [0, 1); then Tn would only have n − 1 fixed points, but Tap − Ta would still work out to ap − a, as needed.)

When 0 < i < p, neither of the terms in the denominator includes a factor of p (relying on the primality of p), leaving the coefficient itself to possess a prime factor of p from the numerator, implying that Modulo p, this eliminates all but the first and last terms of the sum on the right-hand side of the binomial theorem for prime p. ∎ The primality of p is essential to the lemma; otherwise, we have examples like which is not divisible by 4.

Using the Lemma, we have: The proof, which was first discovered by Leibniz (who did not publish it)[4] and later rediscovered by Euler,[3] is a very simple application of the multinomial theorem, which states where and the summation is taken over all sequences of nonnegative integer indices k1, k2, ..., km such the sum of all ki is n. Thus if we express a as a sum of 1s (ones), we obtain Clearly, if p is prime, and if kj is not equal to p for any j, we have and if kj is equal to p for some j then Since there are exactly a elements such that kj = p for some j, the theorem follows.

(This proof is essentially a coarser-grained variant of the necklace-counting proof given earlier; the multinomial coefficients count the number of ways a string can be permuted into arbitrary anagrams, while the necklace argument counts the number of ways a string can be rotated into cyclic anagrams.

[5] This proof uses neither the Euclidean algorithm nor the binomial theorem, but rather it employs formal power series with rational coefficients.

This proof,[3][6] discovered by James Ivory[7] and rediscovered by Dirichlet,[8] requires some background in modular arithmetic.

Let us assume that a is positive and not divisible by p. The idea is that if we write down the sequence of numbers and reduce each one modulo p, the resulting sequence turns out to be a rearrangement of Therefore, if we multiply together the numbers in each sequence, the results must be identical modulo p: Collecting together the a terms yields Finally, we may “cancel out” the numbers 1, 2, ..., p − 1 from both sides of this equation, obtaining There are two steps in the above proof that we need to justify: We will prove these things below; let us first see an example of this proof in action.

If a = 3 and p = 7, then the sequence in question is reducing modulo 7 gives which is just a rearrangement of Multiplying them together gives that is, Canceling out 1 × 2 × 3 × 4 × 5 × 6 yields which is Fermat's little theorem for the case a = 3 and p = 7.

Note that the conditions under which the cancellation law holds are quite strict, and this explains why Fermat's little theorem demands that p is a prime.

Furthermore, the numbers a, 2a, ..., (p − 1)a must all be distinct after reducing them modulo p, because if where k and m are one of 1, 2, ..., p − 1, then the cancellation law tells us that Since both k and m are between 1 and p − 1, they must be equal.

To summarise: when we reduce the p − 1 numbers a, 2a, ..., (p − 1)a modulo p, we obtain distinct members of the sequence 1, 2, ..., p − 1.

Both the rearrangement property and the cancellation law (under the generalized form mentioned above) are still satisfied and can be utilized.

The idea is to recognise that the set G = {1, 2, ..., p − 1}, with the operation of multiplication (taken modulo p), forms a group.

Taking this on faith for the moment, let us assume that a is in the range 1 ≤ a ≤ p − 1, that is, a is an element of G. Let k be the order of a, that is, k is the smallest positive integer such that ak ≡ 1 (mod p).

So p − 1 = km for some positive integer m and then To prove that every element b of G is invertible, we may proceed as follows.

Otherwise, there is some b2 ∈ G\(A∪A1) and we can start all over again, defining A2 as the set whose elements are the numbers b2, ab2, a2b2, ..., ak − 1b2 reduced modulo p. Since G is finite, this process must stop at some point and this proves that k divides p − 1.