%fermatlittle2.tex: Dynamical Systems proof of Fermat's Little Theorem
%ver 2: After suggestions by the editor and referees
\documentclass{amsart}
\usepackage{epsfig}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\begin{document}
\begin{center}
{\Large A Dynamical Systems proof of Fermat's Little Theorem}
\end{center}
\begin{flushright}
Kevin Iga\\
Pepperdine University\\
Malibu, CA 90263\\
\verb+kiga@pepvax.pepperdine.edu+
\end{flushright}
At first glance, the subject of dynamical systems seems unrelated to
number theory. Number theory deals with integers: more specifically,
integer solutions to equations, primes, reducing modulo $n$, and so
on. The study of dynamical systems is concerned with how some
quantities, which depend on time, behave as a function of time, such
as in a differential equation or a recurrence relation.
But in this note we will prove an important and foundational result in
number theory using techniques from dynamical systems. The proof will
be mostly geometric, as is common in dynamical systems, rather than
algebraic, which is common in number theory. This result, known as
Fermat's little theorem, says this:
\begin{theorem}[Fermat]
Let $p$ be a prime number, and $a$ any integer. Then
\[a^p\equiv a\pmod{p}.\]
\end{theorem}
This theorem, not to be confused with its more famous brother,
Fermat's Last Theorem, is useful not only when you want to compute
what $6^{9395}$ is modulo $13$ (though it is useful for that kind of
problem); it is also foundational to the RSA code in modern cryptology (a
readable account of this is in Churchhouse's book on codes
\cite{C}). But its importance goes even beyond this: it, and its
generalizations, turn up often in number theory and abstract algebra.
There are many elementary proofs of this result: almost every number
theory textbook, like Niven and Zuckerman's book {\em An introduction
to the Theory of Numbers} \cite{NZ}, and abstract algebra textbook,
like Artin's {\em Algebra} \cite{A} and Herstein's {\em Topics in Algebra}
\cite{He}, states, proves, and uses this result.
Usually, this is proved using algebraic ideas---sometimes using very
abstract algebraic ideas. In this note we will prove this result
using a simple argument from dynamical systems on the unit interval
$[0, 1]$. The basic idea is to count points of minimum period $p$ of
a particular dynamical system, and noting that this number must be
divisible by $p$.
There was another dynamical systems proof of this result, due to
Hausner \cite{Ha}, pointed out to me by one of the referees of this
paper. That proof produced other impressive results beyond Fermat's
little theorem, but was less visual than this approach.
\begin{proof}
For every integer $n$, we define the function $T_n : [0, 1]\to [0, 1]$
as follows:
\[T_n(x)=\begin{cases}
\{nx\},&x\not=1\\
1,&x=1
\end{cases}
\]
Here the braces denote the fractional part, so that $T_n(x)$ is
between 0 and 1. We can picture $T_n$ in two different but important
ways: first, we can draw a graph. Figure 1 shows a graph of $T_3(x)$.
\begin{figure}
\epsfig{file=t3graph.PS,height=2.3in,width=2.3in}
\caption{The graph of $T_3$}
\end{figure}
Second, we can think of $T_n$ as something that happens to points on the
interval $[0, 1]$. That is, a point at the point $x\in [0, 1]$ gets
``moved to'' the point $T_n(x)$. An ambitious reader might think about
how to visualize this in the case of $T_3(x)$, but the precise picture
is not really important at this point.
What is important is that some points get left where they were (these
are called {\em fixed points}, and occur when $T_n(x)=x$), and some
points get moved somewhere else. We now furthermore imagine that this
operation of applying $T_n$ happens again and again, so that if we
imagine a frog on the interval at point $x$ at time 0, then at time 1,
the frog jumps to $T_n(x)$; at time 2, it is at $T_n(T_n(x))$, and so
on. Then some points in $[0, 1]$ will be periodic, in the sense that
a frog starting at that point will repeat its path over and over again, so that
$T_n(T_n(\dots(T_n(x))))=x$ for some number of iterations of $T_n$.
We call a point $k$-periodic if it comes back after $k$ times, and
call $k$ its minimal period if it doesn't come back for any earlier
time. So the $1$-periodic points are fixed points. Note that there
might be points that never return to their starting position and so are
not periodic at all (it turns out there are many of these when we use
$T_n$ as our function, but that is not important in this proof).
We now determine two crucial properties of the family of functions $T_n$:
\begin{lemma}
Let $n$ be an integer greater than 1. The function $T_n(x)$ has $n$
fixed points in $[0, 1]$.
\end{lemma}
\begin{proof}
Recall that a fixed point of $T_n$ is a point where $T_n(x)=x$. On a graph
of $T_n$, then, this happens when the graph crosses the line $y=x$,
because those are the points where the $x$-value and the $y$-value are equal.
Now figure 1 shows a graph of $T_3$.
Notice that the line $y=x$ crosses this graph in exactly 3 places,
once for each linear segment in the graph. More generally, if $n$ is
a positive integer greater than 1, then there will be $n$ linear
segments, each of slope $n$, and which proceed in $y$-value from $0$
to $1$. In particular, each crosses the line $y=x$ exactly once. So
there are $n$ fixed points of $T_n$ in $[0, 1]$.
\end{proof}
Now for those of you who prefer a more formal, non-visual argument of the
same result:
\begin{proof}
We will now show that the fixed points are of the form $x=\frac{k}{n-1}$
where $k$ is any integer in the range $\{0, 1, ..., n-1\}$. When
$0\le k