## A dynamical proof of Fermat’s little theorem

If you have studied number theory (even just a little bit), you should know the Fermat’s little theorem: for any positive $a$, and for any prime number $p$, we have $a^p\equiv a\pmod p$. Here I will give a proof by using a simple dynamical system.

For $n\in\mathbb{N}$, let $T_n(x) = \cos(n\arccos x)$ (this is also known as Chebyshev polynomial). We will prove the Fermat’s little theorem by analyzing fixed points and orbits of $T_n:[-1,1]\rightarrow[-1,1]$.

Observe that

• For $m,n\in\mathbb{N}$, $T_m\circ T_n = T_{mn}$.
• For any $x\in[-1,1]$, there exists unique $\theta\in[0,\pi]$ such that $\cos{\theta}=x$. Hence solving the equation $T_n(x)=x$ for $x\in[-1,1]$ is equivalent to solving the equation $T_n(\cos{\theta}) = \cos{\theta}$ for $\theta\in[0,\pi]$.
• From now on assume that $n>1$. Clearly, $T_n(\cos{\theta}) = \cos{\theta}$ is just the same as $\cos{n\theta} = \cos{\theta}$. Even high school students know how to solve this. This holds if and only if $\theta = \frac{2k\pi}{n-1}$ or $\frac{2\ell\pi}{n+1}$ for some $k$, $\ell\in\mathbb{Z}$.
• Recall that our $\theta\in[0,\pi]$, so we need $0\leq \frac{2k\pi}{n-1},\frac{2\ell\pi}{n+1}\leq \pi$. By counting, you can see that there are exactly $n$ choices, and hence exactly $n$ solutions to the equation $T_n(\cos{\theta}) = \cos{\theta}$.
• In another words, $T_n$ has exactly $n$ fixed points.

Now let $p$ be a prime number. How many $p$ periodic points does $T_n$ have? That is, what is the number of solutions to the following equation:

$\displaystyle \overbrace{T_n\circ\cdots\circ T_n}^{p\text{ times}}(x) = x?$

By the first observation this is just solving $T_{n^p}(x)=x$, which we know that there are exactly $n^p$ many solutions. But within these $n^p$ solutions, $n$ of them are fixed points of $T_n$, therefore there are $n^p-n$ points in $[-1,1]$ so that they are $p$ periodic points of $T_n$. These periodic points can be decomposed into disjoint union of orbits, while each orbit has exactly $p$ elements. Therefore $p$ divides $n^p-n$.

Since $n>1$ was arbitrary, the Fermat’s little theorem is almost proved. You should know how to prove the case $n=1$!

Reference: “Polynomial Dynamics and a Proof of the Fermat Little Theorem” by Vladimir Dragović.

This entry was posted in Dynamical system, Number Theory. Bookmark the permalink.

### 3 Responses to A dynamical proof of Fermat’s little theorem

1. KKK says:

By p-periodic, do you mean p is the smallest (positive) period?

2. lamwk says:

Yes, sorry that I did not define the terms precisely.

3. reedcanthink says:

A beautiful proof. I have took dynamical course last semester but never thought it could be used to the proof of number theory. Thanks for the sharing.