Why does a Galois field have to have an order of $p^n$ where $p$ is prime?

Question

I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the multiplication factor has to be relatively prime with the size of the alphabet in order for the function to be surjective. Obviously for practical purposes, it would have to be $p^n$ where $p$ is the arity of the number system and $n$ is the bit width of a memory unit. But is there also a theoretical basis for requiring that a Galois field be of size $p^n?$

Answer 1

Fix a finite field $k$ of $q$ elements, with additive identity $0_k$ and multiplicative identity $1_k$.

1. For any integer $n$, let $[n]$ be the $n$-fold sum of $1_k$. Clearly $[a + b] = [a] + [b]$ and $[a\cdot b] = [a] \cdot [b]$. Since $k$ is finite, for any $n$, in the sequence $[a]$, $[a + 1]$, $[a + 2]$, etc., there must be a repeat; let $p$ be the smallest integer so that $[a] = [a + p] = [a] + [p]$. Then $[p] = 0_k$, and in the sequence $[1], [2], [3], \ldots, [p]$, the element $[p]$ is the first zero element.

2. $p$ is called the characteristic of the field. Suppose $p$ were composite, with factors $1 < a \leq b < p$ so that $p = a\cdot b$. Then $0_k = [p] = [a\cdot b] = [a] \cdot [b]$, but $[a]$ and $[b]$ are nonzero because $[p]$ was the first zero element in the sequence $[1], [2], [3], \ldots, [p]$. This is impossible in a field, so $p$ must be prime.

3. The set $\{[0],[1],[2],\ldots,[p-1]\}$ forms a subfield $k_p$ of $k$, since it is by construction closed under addition and multiplication. Thus the extension field $k$ forms a vector space over the subfield $k_p$. Being finite, this vector space is necessarily finite-dimensional, of dimension $n$, and thus has exactly $p^n$ elements. Hence $q = p^n$ for some $n$.