Fermat’s Little Theorem and Finite Prime Fields

By | March 5, 2009

The fact that "\(\mathbb{Z}_p\) is a field if and only if \(p\) is a prime" can be derived from the fact that "every finite integral domain is a field." Also, it is easily derived that every field include a subfield which is isomorphic to one of \(\mathbb{Q}\) or \(\mathbb{Z}_p\) for a prime \(p\). That's why the fields \(\mathbb{Z}_p\) and \(\mathbb{Q}\) are called "prime fields." From the fact that "\(\mathbb{Z}_p\) is a field if and only if \(p\) is a prime," we can derive the Fermat's Little Theorem:

Theorem. (Fermat) If \(p\) is a positive prime number, then the following hold.

(1) For all \(a\in\mathbb{Z}\), \(ap \equiv p \) \( ( {\rm mod} ~ p).\)

(2) if \((a,~p)=1\), that is, if \(a\) and \(p\) are relatively primes, then \(a^{p-1}\equiv 1\) \(({\rm mod}~p).\)

First Proof of Theorem. For any field, the nonzero elements form a group under the field multiplication. In particular, for \(\mathbb{Z}_p\), the elements \(1\), \(2\), \(3\), \(\cdots\), \(p-1\) form a group of order \(p-1\) under multiplication modulo \(p\). Since the order of any element in a group divides the order of the group, we see that for \(b\ne 0\) and \(b\in \mathbb{Z}_p\), we have \(b^{p-1} =1\) in \(\mathbb{Z}_p .\) Using the fact that \(\mathbb{Z}_p\) is isomorphic to the ring of cosets of the form \(a+p\mathbb{Z} ,\) we see at once that for any \(a\in\mathbb{Z}\) not in the coset \(0+p\mathbb{Z},\) we must have \(a^{p-1}\equiv 1 \) \( ({\rm mod}~ p).\) It completes the proof of (2) and (1) follows from (2).

It is used in the proof above that "\(\mathbb{Z}_p\) is a field if and only if \(p\) is a prime" and other properties of ring and coset. In fact, above theorem can be proved not using such preliminaries but using only number theoric facts:

Second Proof of Theorem. First, \(0p \equiv 0\) holds. Second we prove (1) by mathematical induction for \(a.\) First, it is trivial that \(1p \equiv 1\) \( ({\rm mod}~ p).\) Now assume that \(np \equiv n \) for \(n\in\mathbb{N}.\) Then \((n+1)p \equiv (np + 1p) \equiv (n+1) \) \( ({\rm mod}~ p)\) holds by properties of modulo. Thus \( np \equiv n\) for all \(n\in\mathbb{N}.\) Third, \((-n)p \equiv -np \equiv -n\) \( ({\rm mod}~ p)\) and it proves (1). (2) follows from (1).

It is interesting that the proposition "\(\mathbb{Z}_p\) is a field if and only if \(p\) is prime" can be derived from Theorem.

Corollary. \(\mathbb{Z}_p\) is a field if and only if \(p\) is prime.

Proof Assume that \(p\) is prime. Let \(n\) be any element of \(\mathbb{Z}_p\) and \(n\) not equal \(0\) nor \(1\). Then \(n\) and \(p\) are relatively primes, \(n^{p-1} \equiv 1\) \(({\rm mod}~ p)\) holds, thus \(n^{p-2}\) is the multiplicative inverse of \(n\).

Next, assume that \(p\) is not a prime and \(p=rs\) where \(r\) and \(s\) are integers larger than \(1\). Then \(r\) and \(s\) are zero divisors in \(\mathbb{Z}_p , \) thus \(\mathbb{Z}_p\) is not a field.

Leave a Reply