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, Tn(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 T3(x) is illustrated below:

A number x0 is said to be a fixed point of a function f(x) if f(x0) = x0; in other words, if f leaves x0 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 T3(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 Tn(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, Tmn(x) is the composition of Tn(x) and Tm(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 Tm(Tn(x)) is given by

Therefore, what we really need to show is that

To do this we observe that {nx} = nxk, 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 Ta 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


\begin{matrix}
T_{a^p}(x) = & \underbrace{T_a(T_a( \cdots T_a(x) \cdots ))}, \\
& p \, \textrm{ times} \\
\end{matrix}

so any fixed point of Ta(x) is automatically a fixed point of Ta p(x).

We are interested in the fixed points of Ta p(x) that are not fixed points of Ta(x). Let us call the set of such points S. There are a pa points in S, because by Lemma 1 again, Ta(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 Ta. What this means is that we pick a point x0 in S, and repeatedly apply Ta(x) to it, to obtain the sequence of points

This sequence is called the orbit of x0 under Ta. By Lemma 2, this sequence can be rewritten as

Since we are assuming that x0 is a fixed point of Ta p(x), after p steps we hit Ta p(x0) = x0, 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 x0 is not a fixed point of Ta.

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

Read more about this topic:  Proofs Of Fermat's Little Theorem

Famous quotes containing the words proof and/or systems:

    The chief contribution of Protestantism to human thought is its massive proof that God is a bore.
    —H.L. (Henry Lewis)

    The only people who treasure systems are those whom the whole truth evades, who want to catch it by the tail. A system is just like truth’s tail, but the truth is like a lizard. It will leave the tail in your hand and escape; it knows that it will soon grow another tail.
    Ivan Sergeevich Turgenev (1818–1883)