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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s