# Fermat’s Little Theorem and Finite Prime Fields

By | März 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.