Cardinality of Finite Fields

Cardinality of Finite Fields

Achyut Bharadwaj
September 2022
cardinality, finite field, automorphism, characteristic, isomorphism, homomorphism, Fermat's Little Theorem, FLT

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.  


(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$:

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

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

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

  4. 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$

  5. 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$


(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,

(1) $$F=\mathbb{Z}_2[x]/x^2+x+1 = \{0, 1, x, x+1\}$$
We can check that each element of the above has an inverse. Thus $F=\mathbb{Z}_2[x]/x^2+x+1$ is a finite field.
We can similarly check that
(2) $$\mathbb{Z}_2[x]/x^3+x+1$$
is also a finite field.  


(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$:

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

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


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


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


(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.  


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


Every homomorphism between two finite fields is injective.


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


Every finite field has a prime characteristic.


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

A Combinatorial Identity #

In this section, we prove that

(3) $$p\mid\binom{n}{k}\forall k \in [1, n-1]\cap\mathbb{Z}$$
if and only if $n=p^\alpha$ for some positive integer $\alpha$ using elementary methods. This will be used to prove some important properties about automorphisms in the coming sections.
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,
(4) $$p^{v_p(m)}\mid m \text{ but } p^{v_p(m) + 1} \nmid m$$
The following are true:

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

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

(8) $$v_p(n!) = \sum_{j=1}^\infty \left\lfloor \frac{p^\alpha}{p^j} \right\rfloor = \sum_{j=1}^\alpha \left\lfloor p^{\alpha - j} \right\rfloor = p^{\alpha-1} + p^{\alpha-2}+\cdots+1$$
(9) $$\begin{aligned} v_p(k!(n-k)!) &= v_p(k!)+v_p((n-k)!) \\ &= \sum_{j=1}^\infty\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right) \\ &= \sum_{j=1}^\alpha \left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)\end{aligned}$$
since $k$ and $n-k$ are both less than $n$ by assumption. We can take the term $j=\alpha$ outside the summation to get
(10) $$v_p(k!(n-k)! = \sum_{j=1}^{\alpha-1}\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right) + \left\lfloor \frac{k}{p^\alpha} \right\rfloor + \left\lfloor 1-\frac{k}{p^\alpha} \right\rfloor$$
Since $0<\frac{k}{p^\alpha}<1$,
(11) $$\left\lfloor \frac{k}{p^\alpha} \right\rfloor + \left\lfloor 1-\frac{k}{p^\alpha} \right\rfloor = 0 + 0 = 0$$
(12) $$v_p(k!(n-k)! = \sum_{j=1}^{\alpha-1}\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)$$
Now, we use the identity that
(13) $$\left\lfloor x+y \right\rfloor\geq \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor$$
in the above to get that
(14) $$\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\leq \left\lfloor \frac{k}{p^j}+\frac{n-k}{p^j} \right\rfloor = \left\lfloor \frac{n}{p^j} \right\rfloor$$
Since $n=p^\alpha$, $n/p^j = p^{\alpha - j} \in \mathbb{Z}$. Thus,
(15) $$\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\leq p^{\alpha - j}$$
Plugging this into the summation, we get
(16) $$v_p(k!(n-k)!)\leq \sum_{j=1}^{\alpha - 1}p^{\alpha - j}=p^{\alpha - 1}+p^{\alpha - 2} + \cdots + p$$
The RHS of the above equation is strictly less than $p^{\alpha-1} + p^{\alpha-2}+\cdots+1$. Thus,
(17) $$v_p(k!(n-k)!) < v_p(n!)$$
(18) $$v_p(n!) - v_p(k!(n-k)!) = v_p\left(\frac{n!}{k!(n-k)!}\right)=v_p\binom{n}{k}>0$$
This implies that $p\mid \binom nk$ for all $k$ strictly between 0 and $n$, thus completing the first direction of our proof. We now proceed to proving the other direction of the proof. That is, given that $p\mid \binom nk$ for all $k$ strictly between $0$ and $n$, we prove that $n=p^\alpha$.
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
(19) $$v_p(n!) = m(p^{\alpha-1} + p^{\alpha - 2} + \cdots 1)$$
(20) $$v_p(k!(n-k!)) = \sum_{j=1}^\alpha\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)$$
Since $k = p^\alpha$, we may simplify the RHS of the above equation to get
(21) $$v_p(k!(n-k)!) = \sum_{j=1}^\alpha p^{\alpha - j}m = m(p^{\alpha-1}+p^{\alpha - 2} + \cdots + 1)=v_p(n!)$$
Thus, $v_p\binom{n}{k} = 0$, which implies that $p \nmid \binom nk$. If $m\neq1$, then $k$ is between $0$ and $n$. Contradiction. This completes our proof.

Automorphisms of a Finite Field #

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

(22) $$F = \mathbb{Z}_2[x]/x^2+x+1$$
Note that the characteristic of $F$ is $2$. What are the automorphisms over this field? Can we find all of them? Let us find some of them by trying to check whether a map $\sigma\colon F\to F$ is a homomorphism.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
(23) $$\sigma\colon y \mapsto \epsilon y$$
is an automorphism for any $\epsilon\in F$.
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.

(26) $$\sigma(1+x) = (1+x)^3 = x^3 + x^2 + x +1 = x+1$$
(27) $$\sigma(1) + \sigma(x) = 1^3+x^3 = 1 + x +1 = x$$
Thus $\sigma(y) = y^3$ is not an automorphism.
It seems that the only powers of $y$ that are automorphisms are of the form
(28) $$\sigma\colon y \mapsto y^{2^k}$$
However, we also see that the map $\sigma\colon y\mapsto y^5$ is an automorphism (by computing the fifth power of each element and observing that the map is the same as the map from $y$ to $y^2$). But it still holds that the only powers of $y$ that are automorphisms with the power of $y$ less than or equal to $4$ are maps of the form $\sigma\colon y \mapsto y^{2^k}$.
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
(29) $$\sigma(a)\sigma(b) = (a^2+1)(b^2+1) = (ab)^2 + a^2 + b^2 + 1$$
(30) $$\sigma(ab) = (ab)^2 + 1 \neq \sigma(a)\sigma(b)$$
Hence, $\sigma\colon y \mapsto y^2 + 1$ is not an automorphism.
With more examples, it becomes clear that the only automorphisms over $F$ are maps of the form
(31) $$\sigma\colon y \mapsto \epsilon y^{2^k}$$
where $\epsilon\in F$ and $k\in \mathbb{N}$ given that $2^k\leq |F|$. We may generalise this observations to all finite fields as follows:


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

(32) $$\sigma \colon y \mapsto \sum_{r \in S}\epsilon_r y^r$$
where $S$ is some finite nonempty subset of integers and $\epsilon_r$ is an element of $F$ for all $r\in S$. Our approach to prove the theorem is as follows:

  1. 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$.

  2. 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,

(33) $$\sigma(y) = \sum_{r\in S} \epsilon_r y^r$$
Since $S$ is a finite subset of integers, $S$ is bounded below. This implies that $S$ has a minimal element, as can be proven by the well ordering principle. Let $m$ be the minimum element of $S$. Also, let $S’ = S\setminus {m}$. Suppose for the sake of contradiction that $|S| > 1$. In other words, assume for the sake of contradiction that $S’\neq\emptyset$. Now, we take out the term with power $m$ from the summation to get:
(34) $$\sigma(y) = \epsilon_my^m + \sum_{r\in S'} \epsilon_r y^r$$
So, the summation on the RHS will have at least one term. We may take $\epsilon_my^m$ out common from the above to get
(35) $$\sigma(y) = \epsilon_my^m\left(1 + \sum_{r\in S'} {\epsilon_r}\epsilon_m^{-1} y^{r-m}\right)$$
Since $F$ is a field, $\epsilon_m^{-1}\in F$. So, let $\delta_{r-m} = \epsilon_r\epsilon_m^{-1} \in F$.
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
(36) $$\sigma(y) = \epsilon_my^m\left(1 + \sum_{s\in T'} \delta_s y^{s}\right)$$
with none of $s\in T’$ being equal to $0$.
We let $\epsilon_my^m = \phi(y)$ and $1+\sum_{s\in T’}\epsilon_sy^s = \psi(y)$. So, we have
(37) $$\sigma(y) = \phi(y)\psi(y)$$
Since $\sigma$ is an automorphism, it must be multiplicative. It is easy check that $\phi$ is multiplicative. Thus, for $\sigma$ to be an automorphism, $\psi$ must also be multiplicative.
Hence, for all $y\in F$
(38) $$\psi(0) = \psi(0\cdot y) = \psi(0)\cdot\psi(y)$$
For the above to hold, we must have $\psi(0) = 0$ or $\psi(y) = 0$ for all $y\in F$. If $\psi(y) = 0$ for all $y\in F$, then $\sigma(y) = 0$ for all $y\in F$. This contradicts the injectivity of $\sigma$. Hence, $\psi(0) = 0$.
(39) $$\psi(y) = 1+\sum_{s\in T'}\epsilon_sy^s$$
plugging in $y=0$, we get
(40) $$\psi(0) = 1 + \sum_{s\in T'}\epsilon_s(0)^s$$
Since $0\notin T’$, the RHS of the above reduces to $1$. In other words, $\psi(0) = 1$.
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
(41) $$\sigma\colon y \to \epsilon y^n$$
for some integer $n$ and $\epsilon \in F$. Since the $0$ element does not have an inverse, $n$ must be non-negative in order for $\sigma(0)=0$ 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
(42) $$\epsilon^n(a+b)^n =\epsilon^na^n +\epsilon^nb^n$$
for all $a, b \in F$ if and only if $n=p^k$. We may cancel $\epsilon^n$ from both sides of the above since $F$ is a field. So, we are to prove that
(43) $$(a+b)^n = a^n +b^n$$
for all $a,b\in F$ if and only if $n=p^k$. We have,
(44) $$\begin{aligned} (a+b)^n = \sum_{j=0}^n \binom nj a^jb^{n-j} = a^n + b^n + \sum_{j=1}^{n-1}\binom nj a^jb^{n-j}\end{aligned}$$
(45) $$(a+b)^n = a^n + b^n \iff \sum_{j=1}^{n-1}\binom nj a^jb^{n-j}=0\forall a,b\in F$$
If we keep $b$ constant, then
(46) $$P(a) = \sum_{j=1}^{n-1}a^jb^{n-j}$$
is a polynomial in $F[a]$. So, we have that $\sigma$ is an automorphism if and only if $P(a) = 0$ for all $a\in F$. We assumed that the degree of the map is less than or equal to $|F|$. So, $n\leq |F|$, or $n-1 < F$. $P(a)$ has degree $n-1$, and hence has at most $n-1$ roots since $F$ is a field. So, the number of roots of $P(a)$ is less than $|F|$. But all $|F|$ elements of $F$ are roots of $P(a)$. Hence, $P(a)$ must be the zero polynomial. Thus,
(47) $$(a+b)^n = a^n + b^n \iff \binom nj = 0 \text{ in } F\forall j\in[1,n-1]\cap\mathbb{Z}$$
Since $\binom nj \in \mathbb{Z}$, the only way that it reduces to $0$ in $F$ is for it to be a multiple of $p = \text{char}(F)$. Hence,
(48) $$\sigma \text{ is an automorphism in }F \iff p \mid \binom nj\forall j\in[1,n-1]\cap\mathbb{Z}$$
The RHS of the above holds if and only if $n=p^k$ as shown in the previous section. This completes our proof.

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$


(49) $$\sigma\colon y \mapsto \epsilon y$$
By Theorem-1 $\sigma$ is an automorphism. That is, $\sigma$ is bijective. Hence, $\sigma(y)$ returns all elements of $F$.
Consider the products
(50) $$P_1 = \prod_{y\in F^\times} y$$
(51) $$P_2 = \prod_{y\in F^\times}\sigma(y)$$
$F^\times$ is used to denote $F\setminus{0}$. Since $\sigma(y)$ returns all elements of $F$ and $\sigma(0) = 0$, we must have the above two products be equal. So,
(52) $$\prod_{y\in F^\times}y=\prod_{y\in F^\times}\sigma(y)=\prod_{y\in F^\times}\epsilon y = \epsilon^{|F|-1}\prod_{y\in F^\times}y$$
(53) $$\left(\epsilon^{|F|-1}-1\right)\prod_{y\in F^\times}y=\left(\epsilon^{|F|-1}-1\right)P_1=0$$
We cannot have $P_1=0$ since $F$ is an integral domain by Proposition-1. Hence, $\left(\epsilon^{|F|-1}-1\right) = 0$, or
(54) $$\epsilon^{|F|-1} = 1$$
We may multiply both sides of the above by $\epsilon$ to get
(55) $$\epsilon^{|F|} = \epsilon$$
thus completing the proof.

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

(56) $$\sigma\colon y \mapsto y^{|F|}$$
be a map from $F$ onto itself. By Theorem-2, we have $y^{|F|} = y$. So, $\sigma(y) = y$. This implies that $\sigma$ is an automorphism and its degree is less than or equal to $|F|$. Thus, by Theorem-1, we must have $|F| = p^k$ where $p$ is the characteristic of $F$. This completes our proof for the main theorem.

  1. We only need to check that $\sigma$ is a homomorphism since bijectivity follows from Proposition-2↩︎

  2. If $\sigma$ is an automorphism, then $\sigma(0) = 0$. This can be proven in the same way as we proved that $\psi(0)=0$. ↩︎