7.4: Fermat’s Little Theorem

NOTATION. \(\mathbb{Z}_{n}^{*}\) Let \(n \in \mathbb{N}, n \geq 2\). Then \[\mathbb{Z}_{n}^{*}=\mathbb{Z}_{n} \backslash\{[0]\} .\] LEMMA 7.14. Let \(a, n \in \mathbb{Z}, n \geq 2\), be such that \(\operatorname{gcd}(a, n)=1\). Define \(\phi_{a}: \mathbb{Z}_{n}^{*} \rightarrow \mathbb{Z}_{n}^{*}\) by \[\phi_{a}([b])=[a b] .\] Then \(\phi_{a}\) is a permutation of \(\mathbb{Z}_{n}^{*}\). Proof. We show that \([a],[2 a], \ldots,[(n-1) a]\) are distinct elements of \(\mathbb{Z}_{n}^{*}\). Let \(0<i \leq j<n\) and suppose that \(i a \equiv j a \bmod n\). Then \[n \mid j a-i a\] and \[n \mid(j-i) a .\] We assume that \(\operatorname{gcd}(n, a)=1\), so by Proposition \(7.3, n \mid(j-i)\). However \(0 \leq j-i<n\), so \(j-i=0\) and \(i=j\). Hence, if \(0<i<j<n\), \[[i a] \neq[j a] .\] It follows that \(\phi_{a}\) is an injection from \(\mathbb{Z}_{n}^{*}\) to \(\mathbb{Z}_{n}^{*}\). Any injection from a finite set to itself is a surjection, so \(\phi_{a}\) is a permutation of \(\mathbb{Z}_{n}^{*}\).

Definition. Order, \(o_{p}(a)\) Let \(p\) be a prime number and \(a \in \mathbb{Z}\) not a multiple of \(p\). The order of \(a\) in \(\mathbb{Z}_{p}\) is the least \(k \in \mathbb{N}^{+}\)such that \(a^{k} \equiv 1 \bmod p\). We write the order of \(a\) in \(\mathbb{Z}_{p}\) as \(o_{p}(a)\).

If \(a\) is a multiple of \(p\), then the order of \(a\) in \(\mathbb{Z}_{p}\) is undefined, since \(a \equiv 0 \bmod p\), and for all \(k \in \mathbb{N}^{+}\), \[a^{k} \equiv 0 \quad \bmod p .\] The following proposition shows in particular that if \(a\) is not a multiple of \(p\), then the order is well-defined (i.e. that there is some \(k\) with \(a^{k} \equiv 1\) \(\bmod p)\).

PROPOSITION 7.15. Let \(a \in \mathbb{Z}\), and \(p\) be a prime number such that \(p \nmid a\). Then \(o_{p}(a)<p\).

Proof. Let \(p\) be a prime number and \(a \in \mathbb{Z}\) be such that \(a\) is not a multiple of \(p\). By Lemma 7.5, as \(p \nmid a\), then \(p \nmid a^{n}\), and therefore \(\left[a^{n}\right] \in \mathbb{Z}_{p}^{*}\) for any \(n \in \mathbb{N}\). Since \(\left|\mathbb{Z}_{p}^{*}\right|=p-1\), the finite sequence \[\left\langle\left[a^{n}\right] \mid 1 \leq n \leq p\right\rangle\] must have a repetition. Let \(1 \leq n<k \leq p\) be such that \[a^{n} \equiv a^{k} \quad \bmod p .\] Then \[p \mid a^{k}-a^{n} .\] Hence \[p \mid a^{n}\left(a^{k-n}-1\right) .\] However \(p \nmid a^{n}\) and thus by Proposition 7.3, \[p \mid a^{k-n}-1 .\] Thus \[a^{k-n} \equiv 1 \quad \bmod p .\] Therefore \[o_{p}(a) \leq k-n<p .\] Proposition 7.16. Let \(a \in \mathbb{Z}\) and \(p\) be a prime number such that \(a\) is not a multiple of \(p\). Then the remainder classes \([1],[a],\left[a^{2}\right], \ldots,\left[a^{o_{p}(a)-1}\right]\) in \(\mathbb{Z}_{p}\) are distinct.

PROOF. Exercise.

NOTATION. \(S_{a}(n)\) Fix a prime \(p\) for the remainder of this section. Let a be an integer such that \(p \nmid a\). Then for any positive natural number \(n\), we let \(S_{a}(n)\) denote the set of equivalence classes \(\left\{\left[n \cdot a^{k}\right] \mid k \in \mathbb{N}\right\}\) in \(\mathbb{Z}_{p}\). (Although \(S_{a}(n)\) depends on the choice of \(p\), we suppress this in the notation and assume that \(p\) is understood).

LEMMA 7.17. Let \(a \in \mathbb{Z}\) be such that \(p \nmid a\). If \(n \in \mathbb{N}^{+}\)is not a multiple of \(p\), then \[\left|S_{a}(n)\right|=o_{p}(a) .\] Proof. By Proposition 7.15, \(o_{p}(a)<p\). Let \(k=o_{p}(a)\). By Proposition \(7.16\) the remainder classes \([1],[a],\left[a^{2}\right], \ldots,\left[a^{k-1}\right]\) are distinct. Let \(\phi_{n}\) be defined as in Lemma 7.14. Then \(\phi_{n}\) is a permutation of \(\mathbb{Z}_{p}^{*}\). Therefore the remainder classes \([n],\left[n a^{2}\right], \ldots,\left[n a^{k-1}\right]\) are distinct. But \[n a^{k} \equiv n \quad \bmod p,\] SO \[S_{a}(n)=\left\{[n],\left[n a^{2}\right], \ldots,\left[n a^{k-1}\right]\right\}\] (Why?) Therefore \[\left|S_{a}(n)\right|=o_{p}(a)\] LEMMA 7.18. Let \(a \in \mathbb{Z}\) be such that \(p \nmid a\). Then for any \(m, n \in \mathbb{N}^{+}\) which are not multiples of \(p\), the sets \(S_{a}(m)\) and \(S_{a}(n)\) are either equal or disjoint.

PROOF. Suppose \(S_{a}(m) \cap S_{a}(n) \neq \emptyset .\) Let \(m, n \in \mathbb{N}, \operatorname{gcd}(m, p)=1\) \(\operatorname{gcd}(n, p)=1\) and \[\left[m a^{i}\right] \in S_{a}(n)\] Then there is \(j \in \mathbb{N}\) such that \[\left[m a^{i}\right]=\left[n a^{j}\right]\] We may assume that \(i<j\), since there are infinitely many \(j \in \mathbb{N}^{+}\)that satisfy the equation. Then \[[m]=\left[n a^{j-i}\right]\] So \[[m] \in S_{a}(n)\] Therefore if \(S_{a}(m)\) and \(S_{a}(n)\) are not disjoint, we have \[S_{a}(m) \subseteq S_{a}(n)\] By symmetry, we also have \[S_{a}(n) \subseteq S_{a}(m)\] and so either \[S_{a}(m)=S_{a}(n)\] or \[S_{a}(m) \cap S_{a}(n)=\emptyset\] THEOREM 7.19. Fermat’s Little Theorem If \(a \in \mathbb{Z}\) and \(p\) is a prime number such that \(p \nmid a\), then \[a^{p-1} \equiv 1 \quad \bmod p .\] Proof. Let \(k=o_{p}(a)\). We show that \(k \mid(p-1)\). Let \(n \in \mathbb{N}\), where \(n\) is not a multiple of \(p\). By Lemma \(7.17\) \[\left|S_{a}(n)\right|=k .\] By Lemma 7.18, the sets \[\left\{S_{a}(n) \mid n \in \mathbb{N}^{+}, p \nmid n\right\}\] partition \(\mathbb{Z}_{p}^{*}\) into sets of cardinality \(k\). Therefore \(k\) divides \(\left|Z_{p}^{*}\right|\). Since \(\left|Z_{p}^{*}\right|=p-1\), we have \[k \mid(p-1) .\] It follows that there is \(j \in \mathbb{N}\) such that \[a^{p-1} \equiv\left(a^{k}\right)^{j} \equiv 1^{j} \equiv 1 \quad \bmod p .\] COROLLARY 7.20. If \(a \in \mathbb{Z}\) and \(p\) is a prime number such that \(p \nmid a\), then \[a^{p} \equiv a \quad \bmod p .\] Fermat’s Little Theorem is an important result in the theoretical study of prime numbers, and determining primality. How might the theorem be used? Consider the problem of deciding whether a particular natural number \(n\) is prime. In order to determine whether \(n\) is prime, you may invoke the Fundamental Theorem of Arithmetic, and begin checking all the prime numbers up to \(\sqrt{n}\) to determine whether any are non-trivial factors of \(n\). We needn’t check primes greater than \(\sqrt{n}\) since the existence of such a factor entails the existence of a factor less then \(\sqrt{n}\), and by the Fundamental Theorem of Arithmetic, a prime factor less than \(\sqrt{n}\). This may require checking many candidates - in addition to requiring that you know all of the prime numbers smaller than \(\sqrt{n}\), or are willing to check factors that are not prime. For large \(n\) this is a formidable challenge. Alternatively, you can seek \(a \in \mathbb{Z}\) such that \(\left[a^{n}\right] \neq[a]\) in \(\mathbb{Z}_{n}\) in order to determine that \(n\) is not prime.

For instance, is 12,871 prime? We assume that you have access to a computer (doing these computations by hand can be tedious). One approach is to check for factors among the prime numbers less than \(\sqrt{12,871}\), that is the thirty prime numbers less than 114. Alternatively, for \(a \in \mathbb{Z}\), we can check whether \[a^{12,871} \equiv a \quad \bmod 12,871 .\] If the answer is no, then 12,871 is not prime. We shall try \(a=2\) : \[2^{12,871} \equiv 5732 \bmod 12,871 .\] Therefore 12,871 is not prime. If you were to check primes sequentially, you would have to check 18 primes before finding that 61 is the smallest prime that divides 12,871 .

If \(a^{12,871} \equiv a \bmod 12,871\) for a given choice of \(a\), then we can draw no conclusion. In fact there are non-prime numbers, \(n\), such that for any choice of \(a\), \[a^{n} \equiv a \bmod n .\] Numbers that satisfy the conclusion of Theorem 7.19, but are not prime are called Carmichael numbers. So Fermat’s Little Theorem can be used to show that a number is not prime, but not to prove that a number is prime.