# Cardinality of Finite Fields

*Achyut Bharadwaj*

##### September 2022

## Introduction #

A well known theorem about finite fields states the following.

$F$ is a finite field if and only if $|F| = p^k$ for some prime $p$ and positive integer $k$.

In this write-up, we prove the first part of the above theorem, i.e. if $F$ is a finite field, then $|F| = p^k$ using a different approach.

## Introduction to Finite Fields #

We first list down some basic definitions that will be used as we move forward in this write-up.

### Definition-1#

(Field) A field is defined as a set of elements, along with two operations ($+, \cdot$) that satisfies the following, for any $a, b, c \in F$:

$a+(b+c) = (a+b)+c$ and $a\cdot(b\cdot c) = (a\cdot b)\cdot c$

$a+b = b+a$ and $a\cdot b = b\cdot a$

$a\cdot(b+c) = a\cdot b + a\cdot c$

There exists a unique element $0\in F$ such that $a+0 = 0+a = a$ and a unique element $1\in F$ such that $1\cdot a = a\cdot1 = a$

For every $a\in F$, there exists a unique element $-a$ such that $a+(-a)=0$ and a unique element $a^{-1}$ such that $a\cdot a^{-1} = 1$

### Definition-2#

(Finite Field) A finite field is a field with finite cardinality (i.e. with finitely many elements).

Some examples of finite fields are the fields
$\mathbb{Z}_p = {0, 1, 2, \dots, p-1}$ where $p$ is a prime. We can
also have finite fields such as
$\mathbb{Z}_3[i] = {0, 1, 2, i, 2i, 1+i, 1+2i, 2+i, 2+2i}$. Notice
however, that $\mathbb{Z}_2[i] = {0, 1, i, 1+i}$ is not a finite field
since we cannot find a multiplicative inverse for $1+i$. Is there any
other finite field with $4$ elements?

Note that we may write $i$ as a root of the polynomial $x^2+1$ over
$\mathbb{Z}_2$. In other words,
$\mathbb{Z}_2[i] = \mathbb{Z}_2[x]/x^2+1$ (i.e. the quotient ring
obtained modulo $x^2+1$). What if we found another polynomial
$P(x)\in\mathbb{Z}_2[x]$ to replace $x^2+1$ so that
$\mathbb{Z}_2[x]/P(x)$ has $4$ elements and is a finite field?

Consider $P(x) = x^2+x+1$. Then,

We can similarly check that

### Definition-3#

(Homomorphism) A homomorphism between two fields $(F, +, \cdot)$ and $(G, \oplus, \odot)$ is defined as a map $\sigma \colon F \to G$ such that, for any $a, b \in F$:

$\sigma(a+b) = \sigma(a) \oplus \sigma(b)$

$\sigma(a\cdot b) = \sigma(a)\odot\sigma(b)$

### Definition-4#

(Isomorphism) An isomorphism between two fields is defined as a homomorphism that is bijective.

### Definition-5#

(Automorphism) An automorphism on a field $F$ is defined as an isomorphism from $F$ onto itself.

### Definition-6#

(Characteristic) The characteristic of a field $F$ is defined as the smallest $p\in\mathbb{N}$ such that $\sum_{j=1}^p (1) = 0$, where $1$ is the multiplicative identity and $0$ the additive identity corresponding to $F$. If there does not exist such a positive integer $p$, then the characteristic of $F$ is defined to be $0$.

Now, we list and prove some basic results about finite fields that will be used going forward.

### Proposition-1#

Every finite field is an integral domain. That is, if $ab = 0$ in $F$, then $a=0$ or $b=0$.

### Proposition-2#

Every homomorphism between two finite fields is injective.

### Proposition-3#

A field is finite if and only if it has a non-zero characteristic.

### Proposition-4#

Every finite field has a prime characteristic.

### Proposition-5#

$\text{char}(F)$ divides $|F|$

## A Combinatorial Identity #

In this section, we prove that

Notice that we have two directions to prove. The first being that if $n=p^\alpha$ for some positive integer $\alpha$, then $p$ divides all of $\binom{n}{k}$ with $k$ being an integer strictly between $0$ and $n$.

Before we proceed, we state a notation and list some properties related to it. We will not be proving the properties in this article.

Let $v_p(m)$ denote the highest power of $p$ in the prime factorization of $m$. In other words,

- (5) $$v_p(n!) = \sum_{j=1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor$$
- (6) $$v_p(ab) = v_p(a) + v_p(b)$$
- (7) $$v_p(a/b) = v_p(a) - v_p(b)$$

Now, let $n=p^\alpha$ since we are proving the first direction. So,

The most natural way to proceed is by setting up a contradiction. Assume for the sake of contradiction, that $p\mid \binom nk$ for all $k$ strictly between $0$ and $n$ and $n=p^\alpha m$ where $m$ is an integer such that $1<m<\alpha$. We aim to prove that there exists some value of $k$ for which $p \nmid \binom nk$. The best strategy to do so is to construct such a $k$.

We claim that $k=p^\alpha$ ensures that $p \nmid \binom{n}{k}$.

Similar to as in the previous part, we see that

## Automorphisms of a Finite Field #

Let us take a look at the finite field that we had constructed earlier,

^{1}

Firstly, note that the map $\sigma\colon y \mapsto y$ is an automorphisms as it clearly preserves both multiplication as well as addition. Next, notice that the map $\sigma\colon y \mapsto xy$ is also an automorphism. More generally, we see that the map

Next, we also see that the map $\sigma \colon y \mapsto y^2$ is also a automorphism. We may prove it as follows:

Proving that multiplication is preserved. Consider $a, b \in F$. Then, $\sigma(ab) = (ab)^2$. Moreover, since $\sigma$ is an automorphism, we have

(24) $$\sigma(ab) = \sigma(a)\sigma(b) = a^2b^2 = (ab)^2$$Proving that addition is preserved. Consider $a,b \in F$. Then,

(25) $$\sigma(a+b) = (a+b)^2 = a^2+2ab + b^2 = a^2 + b^2 = \sigma(a) + \sigma(b)$$

However, the map $\sigma \colon y \mapsto y^3$ is not an automorphism as can be seen with a counterexample.

It seems that the only powers of $y$ that are automorphisms are of the form

Can we find automorphisms that don’t map to a power of $y$? Is a map like $\sigma \colon y \mapsto y^2 + 1$ an automorphism?

With $\sigma(y) = y^2+1$, we see that

With more examples, it becomes clear that the only automorphisms over $F$ are maps of the form

### Theorem-1#

The maps from a finite field $F$ onto itself, $\sigma \colon y \mapsto \epsilon y^{p^k}$ are all the automorphisms over $F$ with degree less than or equal to the cardinality of $F$, where $p$ is the characteristic of $F$, $\epsilon$ is an element of $F$ and $k$ is a positive integer.

We work on proving the above theorem throughout this section.

It would be convenient if we could first eliminate the case when
$\sigma$ is a sum of more than one distinct powers of $y$ (such as when
$\sigma = y^2+1$). Once we eliminate this case, we are only left to
prove that $\sigma$ is an automorphism if and only if the power of $y$
in $\sigma$ is a prime power.

We now state this more rigorously. Any automorphism over any finite
field $F$ can be represented as

To prove that $|S| = 1$ for $\sigma$ to be an automorphism. This leaves us with all possible automorphisms being $\sigma\colon y \mapsto \epsilon y^n$ for some integer $n$.

To prove that, given $\sigma\colon y \mapsto \epsilon y^n$, $\sigma$ is an automorphism if and only if $n = p^k$ for some positive integer $k$.

We start with proving $(1)$ above.

We have by assumption,

Now, let $T = {s=r-m\mid r\in S}$ and $T’ = T\setminus{0}$. Since $r\leq m$ for all $r\in S$, we must have $s \geq 0$ for all $s\in T$. Thus, $T’\subset \mathbb{N}$. Also note that $|T| = |S|$ and $|T’|=|S’|$. So, we may rewrite Eq-35 as

We let $\epsilon_my^m = \phi(y)$ and $1+\sum_{s\in T’}\epsilon_sy^s = \psi(y)$. So, we have

Hence, for all $y\in F$

Since

But $\psi(0) = 0$. Hence, $0=1$. A contradiction, since $F$ is a field. Thus, $T’ = \emptyset$, which in turn implies that $|S| = 1$.

Thus, any automorphism $\sigma$ is of the form

^{2}. We can also easily eliminate the case when $n=0$. Therefore, any automorphism is of the form $\sigma\colon y \mapsto \epsilon y^n$ where $n$ is a

*positive*integer.

We now prove that $\sigma\colon y \to \epsilon y^n$ with $n\in \mathbb{N}$ is an automorphism if and only if $n = p^k$ for some positive integer $k$, where $p = \text{char}(F)$. This can be restated as proving that $\sigma$ is both multiplicative and additive if and only if $n = p^k$ since this implies $\sigma$ is an automorphism by Proposition-2. Since $\epsilon y^n$ is multiplicative for all values of $n$, we are only left to prove that $\sigma$ is additive if and only if $n=p^k$.

In other words, we are to prove that

## FlT Equivalent and Proof of the Main Theorem #

In this section, we prove the main theorem, using the work in the previous sections, and the following theorem, that is equivalent to Fermat’s Little Theorem for finite fields:

Given a finite field $F$, for any element $\epsilon\in F$, we have $\epsilon^{|F|} = \epsilon$ in $F$

Let

Consider the products

We now proceed to prove our main theorem. That is, every finite field
has cardinality $p^k$ for some prime $p$.

Let