Planting the fields

We'll assume some basic knowledge. We'll assume familiarity with the various definitions of primes: $p > 1$ is prime if it cannot be factored as a product of two integers greater than $1$; equivalently, whenever integers $a, b$ satisfy $p\ \vert\ ab$, then $p\ \vert\ a$ or $p\ \vert\ b$; equivalently, whenever $p\not{\vert}\ a$, the greatest common divisor of $p$ and $a$ (written $(p,a)$) is $1$. We'll assume familiarity also with unique prime factorization and with basic properties of congruences.

Given a prime $p$, let ${\mathbb{Z}}/p{\mathbb{Z}}$, also written ${\mathbb{F}}_p$, denote the $p$-element set $\{0,1,2,\ldots,p-1\}$, with operations of addition and multiplication defined modulo $p$.

Usually, one thinks of ${\mathbb{F}}_p$ as the set of equivalence classes of integers, where two integers are equivalent if they are congruent modulo $p$; here we consider it instead to be set-theoretically contained in ${\mathbb{Z}}$, because this will prove slightly more convenient later. It's evident that our arithmetic operations are well-defined on this set. We claim that ${\mathbb{F}}_p$ is a field: that the two operations of addition and multiplication satisfy the associative, commutative, and distributive laws, that each operation has an identity (0 for addition and $1$ for multiplication), that every element has an additive inverse, and that every element except 0 has a multiplicative inverse. All of the properties except for the last follow readily from the corresponding properties of addition and multiplication among the integers, so detailed proofs won't be needed. Showing the existence of multiplicative inverses is slightly harder. We give two proofs.

Suppose $a \in {\mathbb{F}}_p, a \neq 0$. Then $p\not{\vert}\ a$, so $(a,p) = 1$. Then, the Euclidean algorithm gives integers $k, l$ such that $ak + pl = 1$ in ${\mathbb{Z}}$; so, $ak \equiv 1$ modulo $p$. Thus, reducing $k$ modulo $p$ gives an inverse for $a$ in ${\mathbb{F}}_p$.

A more constructive proof follows from this

Theorem. (Fermat's Little Theorem) For $a$ any integer, $p\ \vert\ a^p - a$.

Proof. We use induction. If $a = 0$, the statement is obvious. Now, given the statement for $a$, we seek to prove it for $a+1$. But

$$(a+1)^p - (a+1) = \sum_{k=0}^p {p\choose k}a^k - a - 1.$$

For $0 < k < p$, ${p\choose k} = p!/k!(p-k)!$ is divisible by $p$, so the above sum is congruent modulo $p$ to $(a^p + 1) - a - 1 = a^p - a \equiv 0$, giving the induction step. So now the statement holds for all $a \geq 0$. But if $a$ is negative, there is some $a' > 0$ which is congruent to $a$ modulo $p$; since the statement holds for $a'$, it holds for $a$. depth-1pt height7pt width6pt

If $a \in {\mathbb{F}}_p$ is nonzero, Fermat tells us that $p \ \vert\ a(a^{p-1}-1)$; since $p$ is prime, $p \ \vert\ a^{p-1} - 1$, or $a^{p-1} = 1$ in ${\mathbb{F}}_p$. So, $a^{p-2}$ is an inverse for $a$. We now have proved

Fact. ${\mathbb{F}}_p$ is a field.

In particular, nonzero elements of ${\mathbb{F}}_p$ may be meaningfully raised to any integral power, positive or negative.

It may seem confusing to let the numbers $0,1,\ldots,p-1$ denote elements both of ${\mathbb{F}}_p$ and of the integers ${\mathbb{Z}}$, since the operations are defined differently, but the alternative would be notational bureaucracy, so we'll continue relying on context to make the difference clear as long as possible. When we declare explicitly that variables lie in ${\mathbb{F}}_p$, however, all operations done on them will also occur in ${\mathbb{F}}_p$ unless otherwise stated.