If you have studied number theory (even just a little bit), you should know the Fermat’s little theorem: for any positive , and for any prime number , we have . Here I will give a proof by using a simple dynamical system.
For , let (this is also known as Chebyshev polynomial). We will prove the Fermat’s little theorem by analyzing fixed points and orbits of .
- For , .
- For any , there exists unique such that . Hence solving the equation for is equivalent to solving the equation for .
- From now on assume that . Clearly, is just the same as . Even high school students know how to solve this. This holds if and only if or for some , .
- Recall that our , so we need . By counting, you can see that there are exactly choices, and hence exactly solutions to the equation .
- In another words, has exactly fixed points.
Now let be a prime number. How many periodic points does have? That is, what is the number of solutions to the following equation:
By the first observation this is just solving , which we know that there are exactly many solutions. But within these solutions, of them are fixed points of , therefore there are points in so that they are periodic points of . These periodic points can be decomposed into disjoint union of orbits, while each orbit has exactly elements. Therefore divides .
Since was arbitrary, the Fermat’s little theorem is almost proved. You should know how to prove the case !
Reference: “Polynomial Dynamics and a Proof of the Fermat Little Theorem” by Vladimir Dragović.