Elements of abstract algebra

Reproduced below is a chapter from a set of notes on cryptography I wrote a while back. No explicit references are made to cryptography, though the selection of topics is obviously influenced by it.

Introduction

We start with a brief overview of the tools from abstract algebra we shall need for the study of cryptographic techniques. The exposition here is necessarily brief, and readers are encouraged to consult a standard textbook in abstract algebra for a detailed treatment.

Our overview of abstract algebra focuses on a few generalizations of number systems and their properties as abstract mathematical structures. In particular, we consider generalizations of real and complex numbers, of polynomials, and of integers and modular arithmetic. The section culminates in the complete study of finite fields, a versatile tool in the study of cryptographic techniques.

1. Fields

A field is an abstraction of the number-system concept, such as the real numbers and the complex numbers. Every field $k$ is equipped with an addition operation and a multiplication operation that satisfies the usual arithmetic properties, i.e., commutativity, associativity, invertibility, and distributivity. In particular, a field always has an additive identity $0$ a multiplicative identity $1$.

Formally, a field is a set F equipped with an addition operation and a multiplication operation such that the following properties hold:

The set of real numbers $\mathbb{R}$ with usual addition and multiplication is a field. Similarly, the set of complex numbers $\mathbb{C}$ and the set of rational numbers $\mathbb{Q}$ with usual addition and multiplication are also fields.

A field $k_1$ is called a subfield of another field $k_2$ if $k_1 \subseteq k_2$ and if the arithmetic operations of $k_1$ and $k_2$ agree on $k_1$. For example, $\mathbb{Q}$ is a subfield of $\mathbb{R}$, and $\mathbb{R}$ is a subfield of $\mathbb{C}$.

We say that a field $k_2$ is a field extension of another field $k_1$ if $k_1$ is a subfield of $k_2$. For example, $\mathbb{C}$ is a field extension of both $\mathbb{R}$, and $\mathbb{Q}$.

We often speak of structure-preserving mappings in abstract algebra. A field homomorphism from a field $k_1$ to another field $k_2$ is a function $\varphi:k_1 \to k_2$ such that

A field homomorphism $\varphi:k_1 \to k_2$ is said to be a field isomorphism if $\varphi$ is an invertible function. In this case, the inverse function $\varphi^{-1}:k_2 \to k_1$ is also a field isomorphism. We say that two fields $k_1$ and $k_2$ with a field isomorphism $\varphi:k_1 \to k_2$ are said to be isomorphic. Any field-theoretic property of a field is shared by its isomorphic fields, and so we often regard isomorphic fields to be essentially the same.

2. Field characteristic

Given an element $a$ of a field $k$, we often write $n \cdot a$ as a shorthand for the $n$-fold addition $a + a + \cdots + a$. A field $k$ is of characteristic $p$ in case $p$ is the smallest positive integer such that $p \cdot 1 = 0$ in $k$. If no such positive integer exists, then we say that $k$ is of characteristic zero. $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ are fields of characteristic zero.

Let us now construct some fields of finite charateristic. Let $\mathbb{Z}/n\mathbb{Z}$ denote the set of integers equipped with addition and multiplication modulo $n$. Since

$$x = kn + x \text{ mod } n$$

for all choices of $k \in \mathbb{Z}$, we see that $\mathbb{Z}/n\mathbb{Z}$ only contains $n$ unique elements (identified modulo $n$).

Now, for each $x \in \mathbb{Z}/n\mathbb{Z}$, Euclidean algorithm furnishes two integers $m_1$ and $m_2$ such that

$$m_1 x + m_2 n = \operatorname{gcd}(x,n),$$

the greatest common divisor of $x$ and $n$. If $n$ is a prime number, then $\operatorname{gcd}(x,n) = 1$, and so we see that

$$1 = m1_x + m2_n = m1_x$$

modulo $n$. It follows that $\mathbb{Z}/n\mathbb{Z}$ is a field if $n$ is prime.

We observe that $\mathbb{Z}/p\mathbb{Z}$ for a prime $p$ is of characteristic $p$. Indeed, $k1 = k$, which does not equal $0$ modulo $p$ for $1 \leq k \leq p-1$. Moreover, $p1 = 0$ modulo $p$.

Let us now show that $\mathbb{Z}/n\mathbb{Z}$ is a field only if $n$ is prime.

Suppose that $n$ is not prime. If $n = 1$, then $\mathbb{Z}/n\mathbb{Z}$ consists of one element and is thus not a field. If $n \geq 2$, then $n$ has at least two prime factors, and so we can find a positive prime number $p$ strictly less than $n$ that divides $n$. We can then find $m \in \mathbb{N}$ such that $n = pm$.

If $\bar{p}\bar{k} = \bar{1}$ for some $k \in \mathbb{Z}$, then $\bar{p}\bar{k} - \bar{1} = \bar{0}$, and so

$$pk - 1 = nk’$$

for some $k’ \in \mathbb{Z}$. Since $nk’ = pmk’$, we see that

$$p(k-mk’) = 1.$$

Since $p \geq 2$, it follows that $0 < k-mk’ < 1$, which contradicts the assumption that $k-mk’$ is an integer. We thus conclude that $\bar{p}$ has no multiplicative inverse in $\mathbb{Z}/n\mathbb{Z}$, and $\mathbb{Z}/n\mathbb{Z}$ fails to be a field.

Generalizing this phenomenon, we now show that every field of positive characteristic must be of prime characteristic.

Let $n$ be the characteristic of a field $k$. We suppose for a contradiction that $n = km$ for some integers $k,m \geq 2$. Since $k < n$ and $m < n$, we can find elements $x$ and $y$ of $k$ such that $k \cdot x \neq 0$ and $m \cdot y \neq 0$, respectively. We then have

$$0 = n(xy) = (km) \cdot (xy) = (k \cdot x)(m \cdot y).$$

Now, $k$ is a field, and so both $(k \cdot x)$ and $(m \cdot y)$ have multiplicative inverses. It follows that

$$ \begin{align*} 0 &= 0(k \cdot x)^{-1}(m \cdot y)^{-1} \\ &= (k \cdot x)(m \cdot y)(k \cdot x)^{-1}(m \cdot y)^{-1} \\ &= (k \cdot x)(k \cdot x)^{-1}(m \cdot y)(m \cdot y)^{-1} \\ &= (1)(1) = 1, \end{align*} $$ which is evidently absurd. It follows that $n$ must be prime.

We shall build on the above results to classify all finite fields in Section 11

3. Polynomial rings over a field

The polynomial ring over a field $k$ is the set $k[X]$ of polynomials

$$a_n X^n + a_{n-1} X^{n-1} + \cdots + a_1 X + a_0$$

with coefficients $a_n,a_{n-1},\ldots,a_0$ from $k$, equipped with the usual polynomial addition and multiplication. We remark that $k[X]$ cannot, in general, be a field. To see this, we suppose for a contradiction that the first-degree mononial $X$ has a multiplicative inverse $P(X)$, i.e.,

$$X P(X) = 1.$$

Substituting $X = 0$, we obtain $0 = 1$, which is absurd. It follows that $X$ does not have a multiplicative inverse.

Many properties of polynomials from elementary mathematics generalize readily to polynomials over a field. For one, it is possible to perform polynomial long division. In this context, dividing $P(X) \in k[X]$ by another polynomial $S(X) \in k[X]$ with $\operatorname{deg}P \geq \operatorname{Q}$ results in the identity

$$P(X) = S(X)Q(X) + R(X),$$

where $\operatorname{deg} R < \operatorname{deg} S$. This condition implies that $\operatorname{deg} S = \operatorname{deg} P - \operatorname{deg} Q$.

A consequence of polynomial long division is polynomial Euclidean algorithm, which, produces, for each pair of polynomials $P,Q \in k[X]$, a pair of polynomials $S,T \in k[X]$ such that

$$PS + QT = \operatorname{gcd}(P,Q).$$

Here $\operatorname{gcd}(P,Q)$ is the polynomial with the highest degree among the polynomials with leading coefficient 1 that divide both $P$ and $Q$.

Analogous to polynomial factorization from elementary mathematics, a polynomial $P \in k[X]$ is said to be reducible if there are polynomials $Q,R \in k[X]$ such that $Q \not\in k$, $R \not\in k$, and $P(X) = Q(X) R(X)$. A polynomial is said to be irreducible if there are no such polynomials. For example,

$X^2 - 1 = (X + \sqrt{2})(X-\sqrt{2}),$

and so $X^2 - 1$ is reducible in $\mathbb{R}[X]$. Nevertheless, neither $X+\sqrt{2}$ nor $X-\sqrt{2}$ is an element of $\mathbb{Q}[X]$, and so $X^2 - 1$ is irreducible in $\mathbb{Q}[X]$.

We can also generalize the concept of the root of a polynomial from elementary mathematics. Here, a root of a polynomial $P(X) \in k[X]$ is an element $a$ of $k$ such that $P(a) = 0$ in $k$. We now divide $P(X)$ by $X-a$ to obtain

$$P(X) = (X-a)Q(X) + R(X),$$

where $\operatorname{deg}R < \operatorname{deg}(X-a) = 1$. It follows that $R(X)$ must be a constant. Since

$$0 = P(a) = (a-a)Q(a) + R(a) = R(a),$$

it follows that $R(X) = 0$, whence

$$P(X) = (X-a)Q(X).$$

A consequence of the above factor theorem is that $P$ cannot have more roots than $\deg P$.

4. Algebraic closure

Recall that a root of a polynomial $P(X) \in k[X]$ is an element $a$ of the base field $k$ such that $P(a) = 0$. We note that not every polynomial has a root. Indeed, the roots of the $X^2 - 1$ are $\sqrt{2}$ and $-\sqrt{2}$, neither of which is in $\mathbb{Q}$. If every non-constant polynomial in $k[X]$ has a root in $k$, then the base field $k$ is said to be algebraically closed. For example, the complex field $\mathbb{C}$ is algebraically closed by the fundamental theorem of algebra.

Recall now that we were able to obtain the roots of $X^2 - 1$ by considering a larger base field, say, $\mathbb{R}$. In fact, given a field $k$, it is always possible to construct a field extension $k^{\text{al}}$ of $k$ that is algebraically closed. We say that $k^{\text{al}}$ is an algebraic closure of $k$. For example, $\mathbb{C}$ is an algebraic closure of $\mathbb{R}$.

A polynomial $P(X) \in k[X]$ is said to be separable if its roots are distinct in $k^{\text{al}}$. For example, $X^2+1$, an element of $\mathbb{R}[X]$, is a separable polynomial, as its roots are $i$ and $-i$.

A field $k$ is said to be perfect if every irreducible polynomial in $k[X]$ is separable. Examples of perfect fields include fields of characteristic zero, finite fields, and algebraically closed fields. The perfect field condition often serves as a simplifying assumption in field theory.

5. Abelian groups

Sometimes, we do not need to consider both multiplication and addition. For example, studying the arithmetic of a 12-hour clock only requires hour addition (addition modulo 12). While multiplication modulo 12 makes perfect sense, it does not any meaning in the context of clock arithmetic.

For such a case, we make use of an Abelian group, which comes equipped only with the addition operation. Formally, an Abelian group is a set $A$ with an addition operation $+$ such that

$\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ the usual addition operation are abelian groups. In addition, the set of integers $\mathbb{Z}$ with the usual addition operation is an abelian group.

We say that an abelian group $A$ is a subgroup of another abelian group $B$ if $A \subseteq B$ and if the addition operations of $A$ and $B$ agree on $A$. For example,

$$\mathbb{Z} \leq \mathbb{Q} \leq \mathbb{R} \leq \mathbb{C},$$

where $\leq$ denotes the subgroup relation.

A group homomorphism from an abelian group $A$ to another abelian group $B$ is a function $\varphi:A \to B$ such that

6. Quotient groups.

The kernel of a group homomorphism $\varphi:A \to B$ is the subgroup

$\ker \varphi = \lbrace a \in A: \varphi(a) = 0\rbrace.$

The kernel $\ker \varphi$ measures how close to an isomorphism $\varphi$ is. Indeed, $\varphi$ is one-to-one if and only if $\ker \varphi = \lbrace 0\rbrace$. In general, we have that

$$\varphi(a) = \varphi(b) \hspace{1em} \text{if and only if} \hspace{1em} a-b \in \ker\varphi.$$

In other words, if $a$ and $b$ differ by an element of the kernel, then $a$ and $b$ are essentially the same as far as $\varphi$ is concerned.

In light of this observation, we define the quotient group $A/S$ of an abelian group $A$ by its subgroup $S$ to be the set of cosets

$$\bar{a} = a + S = \lbrace a + x: x \in S\rbrace,$$

with the addition operation defined by the formula

$$\bar{a} + \bar{b} = \overline{a+b}.$$

We note that cosets of $S$ divide $A$ into equal-sized, non-intersecting partitions. Indeed, the size of each coset is precisely the size of $S$. Moreover, if there exists $p \in (a+S) \cap (b+S)$, then

$$a+x_1 = p = b+x_2$$

for some $x_1,x_2 \in S$. It follows that $a = b+(x_2 - x_1)$ and $b = a+(x_1 - x_2)$, whence $a+S = b + S$. We conclude that distinct cosets do not intersect.

Cosets allow us to can establish a combinatorial restriction on the structure of Abelian groups. To this end, we define the order of an element $x$ of an Abelian group $A$ to be the smallest positive integer $n$ such that $n \cdot x = 0$, where $n \cdot x$ denotes the $n$-fold sum of $x$. We often write $\vert x \vert$ to denote the order of $x$.

We now fix $x \in A$ and define the subgroup of $A$ generated by $x$:

$$\langle x \rangle = \lbrace n \cdot x : n \in \mathbb{Z}\rbrace.$$

Here, $n \cdot x$ with $n < 0$ denotes the $\vert n \vert$-fold sum of $(-x)$. Evidently, $\vert \langle x \rangle \vert$ is the order of $x$.

Since cosets of $\langle x \rangle$ divide $A$ into equal-sized, non-intersecting partitions, we see that

$$\vert A \vert = \vert \langle x \rangle \vert \vert A/\langle x \rangle \vert.$$

In particular, the order of $x$ must divide the cardinality of $A$. This fact is commonly known as Lagrange’s theorem.

Since quotient groups collapse a subgroup into one element by declaring equivalence, we can do away with the kernel of a group homomorphism $\varphi:A \to B$ by considering its induced homomorphism $\bar{\varphi}:A/\ker \varphi \to B$, defined by the formula

$$\varphi(\bar{a}) = \varphi(a).$$

Indeed, observe that

$$ \begin{align*} &\varphi(a) = \varphi(b) \\ \Leftrightarrow& a - b \in \ker \varphi \\ \Leftrightarrow& \bar{a} = \bar{b} \text{ in } A/\ker\varphi, \end{align*} $$

whence $\ker \bar{\varphi} = \lbrace \bar{0}\rbrace.$ It now follows that $A/\ker \varphi$ is isomorphic to

$$\operatorname{im}\varphi = \lbrace \varphi(a): a \in A\rbrace,$$

a subgroup of $B$. This fact is referred to as the first isomorphism theorem.

7. Cyclic groups

The first isomorphism theorem can be used to furnish a complete classification of a special type of groups, called cyclic groups. An abelian group $C$ is said to be cyclic if there exists an element $g$, called a generator of $C$, such that every element of $C$ can be written as an $n$-fold sum of $g$ for some $n \geq 1$. The standard example of a cyclic group is $\mathbb{Z}$, the group of integers.

Given a cyclic group $C$, we can construct a group homomorphism $\varphi:\mathbb{Z} \to C$ by setting

$$\varphi(n) = n \cdot g,$$

where $n \cdot g$ is the $n$-fold sum $g + g + \cdots + g$ of a generator $g$ of $C$. This mapping is necessarily surjective, as all elements of $C$ are of the form $n \cdot g$.

If $\varphi$ is one-to-one, then $\varphi$ is an isomorphism, and so

$$C \cong \mathbb{Z}.$$

If $\varphi$ fails to be injective, then the first isomorphism theorem implies that

$$C \cong \mathbb{Z}/\ker \varphi.$$

Now, every subgroup of $\mathbb{Z}$ must be of the form

$$n \mathbb{Z} = \lbrace kn: k \in \mathbb{Z}\rbrace,$$

and so

$$C \cong \mathbb{Z}/n\mathbb{Z}$$

for some $n \geq 1$. We remark that $\mathbb{Z}/n\mathbb{Z}$ has precisely $n$ elements:

$$\mathbb{Z}/n\mathbb{Z} = \lbrace \bar{0},\bar{1},\ldots,\overline{n-1}\rbrace.$$

It follows that every cyclic group is isomorphic to either $\mathbb{Z}$ or $\mathbb{Z} / \mathbb{Z}$ for some $n \in \mathbb{Z}$.

We now establish a condition under which an Abelian group must be cyclic: if the size of $A$ is prime, then $A$ must be cyclic. To see this, we recall Lagrange’s theorem from Section 6, which states that the order of each element must divide the size of the group. If $\vert A \vert = p$ is prime, then every element of $A$ must be either of order $1$ or $p$. Since only the additive identity $0$ can be of order 1, it follows that at least one element of $A$ is of order $p$, which is a generator of $A$.

8. Cauchy’s Theorem on Abelian groups

Using the theory of cyclic groups, we can show that every finite Abelian group whose order is dividible by a prime number $p$ contains an element of order $p$. This result, known as Cauchy’s theorem, is to be understood as a partial converse to Lagrange’s theorem.

We proceed by induction on the order of the group. Let $A$ be an Abelian group of order $pm$. If $m=1$, then $A$ is a group of prime order, hence cyclic. (See Section 7) It follows that $A$ contains an element of order $p$.

Fix $m > 1$ and suppose that every Abelian group of order $pn$ for each $1 \leq n < m$ contains an element of order $p$. Let $a$ be a non-identity element of $A$. If the order of $a$ is divisible by $p$, then $k \cdot a$ for some $k \geq 1$ is of order $p$.

If not, then $G / \langle a \rangle$ is an Abelian group of order $pn$ for some $1 \leq n < m$, whence it contains an element $h + \langle a \rangle$ of order $p$. This implies that $(p \cdot h) + \langle a \langle = \langle a \langle$, i.e., $p \cdot h = k \cdot a$ for some $k \geq 1$. We observe that

$$\operatorname{lcd}(k, \vert a \vert) \cdot a = 0,$$

where $\operatorname{lcd}$ is the least common multiple function. Therefore,

$$\left( p , \operatorname{lcd}(k, \vert a \vert) \right) \cdot h = 0,$$

and so $\vert h \vert$ is a multiple of $p , \operatorname{lcd}(k, \vert a \vert)$. In particular, the primality of $p$ implies that $\vert h \vert = lp$ for some $l \geq 1$, whence $l \cdot h$ is an element of $G$ of order $p$. By induction, every Abelian group whose order is divisible by $p$ contains an element of order $p$.

This completes the proof of Cauchy’s theorem.

9. Direct sums of Abelian groups

Complex groups can be built from simpler groups by piecing them together. This is the main idea of the direct sum of Abelian groups.

Given Abelian groups $A$ and $B$, their direct sum is the cartesian product

$$A \oplus B = \lbrace (a,b): a \in A, b \in B\rbrace$$

with the addition operation defined coordinatewise:

$$(a_1,b_1) + (a_2,b_2) = (a_1+a_2,b_1+b_2).$$

We note that if $\vert A \vert = n$ and $\vert B \vert = m$, then $\vert A \oplus B\vert = nm$.

The main theorem about direct sums of Abelian groups is that every finite Abelian group is a direct sum of cyclic groups. Specifically, if $A$ is an Abelian group with $n$ elements, then

$$A \cong \mathbb{Z}/p_1\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/p_k\mathbb{Z},$$

where $p_1,\ldots,p_k$ are powers of prime numbers such that $p_1 \cdots p_k = n$. The proof of this fact is long and technical, and so we omit it.

We now establish a condition under which the direct sum of two cyclic groups is cyclic. The theorem is commonly referred to as the Chinese remainder theorem and states that

$$\mathbb{Z}/m\mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/(mn)\mathbb{Z}$$

if $m$ and $n$ are relatively prime. Indeed, if $g$ and $h$ are generators of $\mathbb{Z}/m\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$, respectively, then $(g,h)$ must be of order $mn$ in $\mathbb{Z}/,m\mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z}$, as $m$ and $n$ are relatively prime. This implies that $(g,h)$ is a generator of $\mathbb{Z}/m\mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z}$, which is then a cyclic group of order $mn$. Since we have seen in Section 7 that there is, up to an isomorphism, only one cyclic group of each order, the isomorphism result follows.

10. Quotients of polynomial rings

The quotient structure on Abelian groups we have studied in Sections 1.6 through 1.9 can be adopted to study rings of polynomials, introduced in Section 3.

Let $k$ be a field. We note that $k[X]$, equipped just with polynomial addition, is an Abelian group. Which subgroups of the additive Abelian group $k[X]$ play nicely with the multiplicative structure of the polynomial ring $k[X]$?

We define the ideal of the polynomial ring $k[X]$ generated by a polynomial $P(X) \in k[X]$ to be the set

$$(P) = \lbrace S(X) P(X) : S(X) \in k[X]\rbrace.$$

We observe that $(P)$ is a subgroup of the additive Abelian group $k[X]$. Moreover, if $Q(x) \in (P)$ and $S(X) \in k[X]$, then the products $QS$ and $SQ$ also belong to $(P)$.

Analogous to the Abelian-group case, we define a coset of $(P)$ to be a set of the form

$$\bar{Q} = Q + (P) = \lbrace Q(X) + R(X) : R(X) \in (P)\rbrace$$

for some $Q(X) \in k[X]$. We define addition of cosets

$$[Q_1 + (P)] + [Q_2 + (P)] = [Q_1 + Q_2] + (P)$$

and multiplication of cosets

$$[Q_1 + (P)][Q_2 + (P)] = [Q_1Q_2] + (P).$$

The quotient ring $k[X]/(P)$ is defined to be the set of all cosets of $(P)$, equipped with coset addition and coset multiplication.

$k[X]$ is an Abelian group, and $(P)$ is a subgroup, we see that $k[X]/(P)$ is also an Abelian group. When is $k[X]/(P)$ a field? Answering this question boils down to checking when coset multiplication is invertible.

We recall from Section 3 that a polynomial $P(X) \in k[X]$ is irreducible if there are no non-constant polynomials $R(X), S(X) \in k[X]$ such that $P(X) = R(X) S(X)$. We shall show that $k[X] / (P)$ is a field if $P$ is irreducible.

Let $Q \in k[X] \smallsetminus (P)$; in other words, let $Q + (P)$ be a nonzero element of $k[X]/(P)$. The polynomial Euclidean algorithm, introduced in Section 3, furnishes polynomials $S,T \in k[X]$ such that

$$PS + QT = \operatorname{gcd}(P,Q).$$

$P$ is irreducible, and $Q$ is not a multiple of $P$, and so $\operatorname{gcd}(P,Q) = 1$. It follows that

$$[QT] + (P) = [QT + PS] + (P) = 1 + (P),$$

the multiplicative identity in $k[X]/Q$. It follows that every nonzero element in $k[X]/(P)$ is invertible, whence $k[X]/(P)$ is a field.

11. Classification of finite fields

We are finally equipped to exhibit all finite fields, up to isomorphisms.

To start off, we show that every finite field must be of size $p^n$, where $p$ is a prime and $n \geq 1$.

We first remark that every finite field must have positive characteristic. Indeed, if a field $k$ is of characteristic 0, then $\lbrace m \cdot 1: m \geq 1\rbrace$ is an infinite subset of $k$, whence $k$ must be infinite.

We have established in Section 1.2 that every field of positive characteristic must be of prime characteristic. We therefore let $k$ be a finite field of characteristic $p$, a prime. Then

$$\langle 1 \rangle = \lbrace m \cdot 1: m \in \mathbb{Z}\rbrace$$

is of size $p$. Now, if we consider $k$ as an Abelian group with respect to its addition operation, then $\langle 1 \rangle$ is a subgroup of size $p$. It follows from Lagrange’s theorem that the size of $k$ must be divisible by $p$.

We now suppose for a contradiction that another prime $q$ also divides the cardinality of $k$. Considering, once again, $k$ as an Abelian group with respect to its addition operation, we invoke Cauchy’s theorem to find an element $x \in k$ of order $q$. This means that $x \neq 0$, and that $q \cdot x = 0$. Since $k$ is of characteristic $p$, we also have that $p \cdot x = 0$.

The Euclidean algorithm furnishes two integers $m_1$ and $m_2$ such that

$$m_1p + m_2q = \operatorname{gcd}(p,q),$$

the greatest common divisor of $p$ and $q$. Since $p$ and $q$ are distinct primes, $\operatorname{gcd}(p,q) = 1$.

It now follows that

$$x = 1 \cdot x = (m_1p+m_2q) \cdot x = m_1 \cdot (p \cdot x) + m_2 \cdot( q \cdot x) = 0,$$

which contradicts the fact that $x \neq 0$. We conclude that no other prime divides the cardinality of $k$; in other words, $\vert k \vert = p^n$ for some $n \geq 1$.

We now show that, up to an isomorphism, there is precisely one field of each size. For this reason, we write $\mathbb{F}_{p^n}$ to denote the field of size $p^n$.

To this end, we define the multiplicative group of a field $k$ to be the set

$$k^* = k \smallsetminus \lbrace 0\rbrace.$$

equipped with the multiplication operation. Every element is invertible with respect to the multiplicative identity $1$. And, of course, it follows from the properties of the multiplication operation on $k$ that

We recall that every finite Abelian group is a direct sum of cyclic groups. Specifically, we have that

$$k^* \cong \mathbb{Z}/q_1\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/q_m\mathbb{Z},$$

where $q_1,\ldots,q_m$ are powers of prime numbers such that $q_1 \cdots q_m = p^n-1$. This decomposition implies that, if $q$ is the least common multiple of $q_1,\ldots,q_m$, then $x^q = 1$ for all $x \in k^*$.

By the factor theorem, the polynomial $X^q-1$ cannot have more than $q$ roots, and so $q \geq p^n-1$. Now $q = \operatorname{lcd}(q_1,\ldots,q_m) \leq q_1 \cdots q_m = p^n-1$, and so $q \leq p^n-1$. It follows that $q = p^n-1$.

Now, for each $1 \leq i \leq m$, we let $x_i$ be a generator of $\mathbb{Z}/q_i\mathbb{Z}$, so that $\vert x_i \vert = q_i$. The $m$-tuple $(x_1,x_2,\ldots,x_m)$ is an element of $\mathbb{Z}/q_1\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/q_m\mathbb{Z}$ whose order is $q$. Observe that $q = p^n-1$ implies that $\mathbb{Z}/q_1\mathbb{Z} \oplus \cdots \oplus \mathbb{Z}/q_m\mathbb{Z}$ is a cyclic group. It follows that $k^*$ is a cylic group of order $p^n-1$, whence

$$k^* \cong \mathbb{Z}/(p^n-1)\mathbb{Z}.$$

We have shown that every field of order $p^n$ can admit only one multiplicative structure, from which it follows that every field of size $p^n$ is isomorphic.

It remains to construct $\mathbb{F}_{p^n}$ for each $p$ and every $n$. We have established in Section 2 that

$$\mathbb{F}_p \cong \mathbb{Z}/p\mathbb{Z}.$$

We shall construct $\mathbb{F}_{p^n}$ from $\mathbb{F}_p$ by taking a quotient of the polynomial ring $\mathbb{F}_p[X]$, a method introduced in Section 10. We take for granted the existence of an irreducible polynomial $P$ of degree $n$. We omit the long, technical proof. Interested readers can consult, for example, a blog post over at everything2.com.

We claim that $\mathbb{F}_p[X]/(P)$ is a field of size $p^n$. We have shown in Section 10 that the irreducibility of $P$ implies that $\mathbb{F}_p[X]/(P)$ is a field. It suffices to show that $\mathbb{F}_p[X]/(P)$ has $p^n$ elements.

Let $S \in \mathbb{F}_p[X]$. If $\deg(Q) \geq n$, then polynomial long division yields

$$S(X) = P(X)Q(X) + R(X),$$

where $\deg R < n$. Therefore,

$$S + (P) = [PQ+R] + (P) = R + (P),$$

whence it suffices to consider polynomials of degree less than $n$. Since there are $p$ possible field elements for each coefficient, we conclude that there are $p^n$ unique polynomials of degree less than $n$. It now follows that the size of $\mathbb{F}_p[X]/(P)$ is $p^n$, as was to be shown.