1 Fermat’s Little Theorem
1.1 Statement
Fermat’s Little Theorem: for any prime \(p\) and integer \(a\), \(a^p \equiv a \pmod{p}\).
Fermat’s Little Theorem (natural-number form): for any prime \(p\) and natural number \(a\), \(a^p \equiv a \pmod{p}\).
The natural-number form of Fermat’s Little Theorem implies the integer form; that is, definition 2 implies definition 1.
Working in \(\mathbb {Z}/p\mathbb {Z}\), every element is the cast of its natural-number representative \(b := (a \bmod p).val \in \mathbb {N}\). Applying the natural-number form to \(b\) gives \(b^p \equiv b \pmod p\), which lifts back through the canonical map to \(a^p \equiv a \pmod p\).
1.2 Proof using Binomial theorem
For any prime \(p\) and integer \(a\), we have \(a^p \equiv a \pmod{p}\).
Use Freshmen’s dream: \((a + b)^p = a^p + b^p\) in characteristic \(p\). Then \((a + 1)^p \equiv a^p + 1 \pmod{p}\), and the result follows by induction on \(a\).
1.3 Proof using Lagrange’s theorem
For any prime \(p\) and integer \(a\), we have \(a^p \equiv a \pmod{p}\).
If \(a\) is divisible by \(p\), then \(a^p \equiv 0 \equiv a \pmod{p}\). Assume that \(a\) is not divisible by \(p\). Consider the multiplicative group \((\mathbb {Z}/p\mathbb {Z})^\times \) of nonzero elements modulo a prime \(p\). This group has order \(p-1\). By Lagrange’s theorem, the order of any element divides the order of the group. Therefore, for any integer \(a\) not divisible by \(p\), we have \(a^{p-1} \equiv 1 \pmod{p}\).
1.4 Proof using Dynamical Systems
For a natural number \(n\) (\(\ge 2\)), define \(T_n : [0, 1] \to [0, 1]\) by \(T_n(x) = \{ nx\} \) for \(0 \le x {\lt} 1\) and \(T_n(1) = 1\), where \(\{ y\} \) denotes the fractional part of \(y\).
For any natural numbers \(m, n\), the composition of \(T_m\) and \(T_n\) equals \(T_{mn}\), i.e., \(T_m \circ T_n = T_{mn}\).
If \(x = 1\), then both sides equal \(1\). Otherwise \(T_n(x) = \{ nx\} \in [0, 1)\), and \(T_m(T_n(x)) = \{ m \{ nx\} \} \). Writing \(m \{ nx\} = mnx - m\lfloor nx \rfloor \) and noting that \(m \lfloor nx \rfloor \in \mathbb {Z}\), we have \(\{ m \{ nx\} \} = \{ mnx\} = T_{mn}(x)\).
For any \(n \ge 2\), the map \(T_n\) has exactly \(n\) fixed points.
For \(x \in [0, 1)\), the equation \(T_n(x) = x\) becomes \(\{ nx\} = x\), i.e., \((n-1)x \in \mathbb {Z}\). With \(x \in [0, 1)\), this gives \(x = j/(n-1)\) for \(j \in \{ 0, 1, \dots , n-2\} \), contributing \(n - 1\) fixed points. Together with the fixed point \(x = 1\), this gives exactly \(n\) fixed points.
For any prime \(p\) and integer \(a\), we have \(a^p \equiv a \pmod{p}\).
By the standard reduction to the natural-number version, it suffices to prove the statement for natural numbers. The cases \(a = 0\) and \(a = 1\) are trivial; assume \(a \ge 2\). Let \(S\) be the set of fixed points of \(T_{a^p}\) that are not fixed points of \(T_a\). By lemma 8 applied to \(T_{a^p}\) and \(T_a\), \(S\) has \(a^p - a\) elements. For each \(x_0 \in S\), since \(x_0\) is fixed by \(T_{a^p} = T_a^p\) (using lemma 7 iteratively), the \(T_a\)-orbit of \(x_0\) has size dividing \(p\). Because \(p\) is prime, the size is \(1\) or \(p\); size \(1\) would make \(x_0\) a fixed point of \(T_a\), which is excluded. Hence every orbit has exactly \(p\) elements, and these orbits partition \(S\). Therefore \(p\) divides \(|S| = a^p - a\).