Proofs of Fermat's Little Theorem - Proof Using Dynamical Systems

Proof Using Dynamical Systems

This proof uses some basic concepts from dynamical systems.

We start by considering a family of functions, T_n(x), where n ≥ 2 is an integer, mapping the interval to itself by the formula

where {y} denotes the fractional part of y. For example, the function T₃(x) is illustrated below:

A number x₀ is said to be a fixed point of a function f(x) if f(x₀) = x₀; in other words, if f leaves x₀ fixed. The fixed points of a function can be easily found graphically: they are simply the x-coordinates of the points where the graph of f(x) intersects the graph of the line y = x. For example, the fixed points of the function T₃(x) are 0, 1/2, and 1; they are marked by black circles on the following diagram.

We will require the following two lemmas.

Lemma 1. For any n ≥ 2, the function T_n(x) has exactly n fixed points.

Proof. There are three fixed points in the illustration above, and the same sort geometrical argument applies for any n ≥ 2.

Lemma 2. For any positive integers n and m, and any 0 ≤ x ≤ 1,

In other words, T_mn(x) is the composition of T_n(x) and T_m(x).

Proof. The proof of this lemma is not difficult, but we need to be slightly careful with the endpoint x = 1. For this point the lemma is clearly true since

So let us assume that 0 ≤ x < 1. In this case,

so T_m(T_n(x)) is given by

Therefore, what we really need to show is that

To do this we observe that {nx} = nx − k, where k is the integer part of nx; then

since mk is an integer.

Now let us properly begin the proof of Fermat's little theorem, by studying the function T_{a p}(x). We will assume that a is positive. From Lemma 1, we know that it has a p fixed points. By Lemma 2 we know that

so any fixed point of T_a(x) is automatically a fixed point of T_{a p}(x).

We are interested in the fixed points of T_{a p}(x) that are not fixed points of T_a(x). Let us call the set of such points S. There are a p − a points in S, because by Lemma 1 again, T_a(x) has exactly a fixed points. The following diagram illustrates the situation for a = 3 and p = 2. The black circles are the points of S, of which there are 32 − 3 = 6.

The main idea of the proof is now to split the set S up into its orbits under T_a. What this means is that we pick a point x₀ in S, and repeatedly apply T_a(x) to it, to obtain the sequence of points

This sequence is called the orbit of x₀ under T_a. By Lemma 2, this sequence can be rewritten as

Since we are assuming that x₀ is a fixed point of T_{a p}(x), after p steps we hit T_{a p}(x₀) = x₀, and from that point onwards the sequence repeats itself.

However, the sequence cannot begin repeating itself any earlier than that. If it did, the length of the repeating section would have to be a divisor of p, so it would have to be 1 (since p is prime). But this contradicts our assumption that x₀ is not a fixed point of T_a.

In other words, the orbit contains exactly p distinct points. This holds for every orbit of S. Therefore, the set S, which contains a p − a points, can be broken up into orbits, each containing p points, so a p − a is divisible by p.