Why Do Finite Fields Have Prime-Power Size?

1. The question

Finite fields are among those mathematical objects whose classification is strikingly rigid: their sizes are exactly the prime powers. But where does that restriction come from, and why does every prime power actually occur?

Suppose $K$ is a finite field. Its characteristic must be a prime $p$, so $K$ contains a copy of the prime field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$. Since $K$ is then a finite-dimensional vector space over $\mathbb{F}_p$, say $\dim_{\mathbb{F}_p}K=n$, it follows immediately that

$$|K|=p^n~.$$

Thus every finite field must have prime-power cardinality. The more interesting direction is existence: for every prime $p$ and every integer $n\ge 1$, can we actually build a field with $p^n$ elements?

The proof below is combinatorial. We count monic irreducible polynomials, package unique factorization into a generating function, and then use Möbius inversion to obtain an explicit formula.

2. Counting monic polynomials by their irreducible factors

Let $a_n$ denote the number of monic irreducible polynomials of degree $n$ in $\mathbb{F}_p[x]$. There are exactly $p^n$ monic polynomials of degree $n$, because a polynomial

$$x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0~,$$

has $p$ independent choices for each coefficient $c_0,\ldots,c_{n-1}$. Since $\mathbb{F}_p[x]$ is a unique factorization domain, every monic polynomial factors uniquely into monic irreducibles.

Suppose a degree-$n$ polynomial contains $m_k$ irreducible factors of degree $k$, counted with multiplicity. Then

$$m_1+2m_2+\cdots+nm_n=n~.$$

For a fixed $k$, choosing a multiset of $m_k$ factors from the $a_k$ available monic irreducibles of degree $k$ gives

$$\binom{m_k+a_k-1}{m_k}~,$$

possibilities. Therefore, summing over every weighted partition of $n$,

$$ \boxed{ p^n= \sum_{m_1+2m_2+\cdots+nm_n=n} \prod_{k=1}^{n}\binom{m_k+a_k-1}{m_k} } $$

This is already a recurrence for the numbers $a_n$, but it is not a pleasant one to use directly. For example, when $p=2$ it gives

$$ \begin{aligned} a_1 &= 2~,\\ a_2+\binom{a_1+1}{2} &= 4~,\\ a_3+a_1a_2+\binom{a_1+2}{3} &= 8~,\\ a_4+a_1a_3+\binom{a_2+1}{2}+\binom{a_1+3}{4} &= 16~, \end{aligned} $$

and hence $a_1=2$, $a_2=1$, $a_3=2$, and $a_4=3$. We now compress the entire recurrence into one generating-function identity.

3. An Euler product for polynomials over $\mathbb{F}_p$

Introduce a formal variable $t$ that records polynomial degree. The generating function for all monic polynomials is simply

$$\sum_{n\ge0}p^n t^n=\frac{1}{1-pt}~.$$

Now fix one monic irreducible polynomial of degree $k$. In a factorization it may occur zero times, once, twice, and so on, contributing

$$1+t^k+t^{2k}+\cdots=\frac{1}{1-t^k}~.$$

Since there are $a_k$ monic irreducibles of degree $k$, all degree-$k$ irreducibles together contribute $(1-t^k)^{-a_k}$. Unique factorization then gives the formal Euler product

$$ \boxed{ \prod_{k\ge1}(1-t^k)^{-a_k}=\frac{1}{1-pt} } $$

This is the polynomial analogue of the way Euler products encode unique factorization of integers: irreducible polynomials play the role of primes, while degree plays the role of a logarithmic size.

3.1 Recovering the same identity from the multiset count

The longer combinatorial recurrence above produces the same formula. Using

$$\sum_{m\ge0}\binom{m+a-1}{m}z^m=(1-z)^{-a}~,$$

we may sum independently over every multiplicity $m_k$:

$$ \sum_{(m_1,m_2,\ldots)}' \prod_{k\ge1}\binom{m_k+a_k-1}{m_k}t^{km_k} = \prod_{k\ge1}\sum_{m\ge0}\binom{m+a_k-1}{m}t^{km} = \prod_{k\ge1}(1-t^k)^{-a_k}~. $$

The prime indicates sequences with only finitely many nonzero entries. Comparing with the generating function for all monic polynomials again yields the boxed identity above.

4. Taking logarithms: a much simpler recurrence

Because we are working with formal power series whose constant term is $1$, formal logarithms are legitimate. Taking logarithms gives

$$-\sum_{k\ge1}a_k\log(1-t^k)=-\log(1-pt)~.$$

Using the correct expansion

$$-\log(1-x)=\sum_{r\ge1}\frac{x^r}{r}~,$$

we obtain

$$ \sum_{k\ge1}a_k\sum_{r\ge1}\frac{t^{kr}}{r} = \sum_{n\ge1}\frac{p^n t^n}{n}~. $$

To extract the coefficient of $t^n$ on the left, we need $kr=n$, so $k$ must divide $n$ and $r=n/k$. Therefore

$$ \frac{1}{n}\sum_{k\mid n}k a_k=\frac{p^n}{n}~, $$

or equivalently

$$ \boxed{\sum_{k\mid n}k a_k=p^n} $$

For $p=2$, this reduces the previous cumbersome system to

$$ \begin{aligned} a_1 &=2~,\\ a_1+2a_2 &=4~,\\ a_1+3a_3 &=8~,\\ a_1+2a_2+4a_4 &=16~, \end{aligned} $$

immediately recovering $2,1,2,3$.

5. Möbius inversion and the exact counting formula

The recurrence has the divisor-sum form required for Möbius inversion. If $F(n)=\sum_{d\mid n}G(d)$, then

$$G(n)=\sum_{d\mid n}\mu(d)F\!\left(\frac{n}{d}\right)~,$$

where the Möbius function is

$$ \mu(n)= \begin{cases} 1, & n=1~,\\ (-1)^r, & n \text{ is a product of }r\text{ distinct primes}~,\\ 0, & n \text{ is divisible by the square of a prime}~. \end{cases} $$

Taking $F(n)=p^n$ and $G(n)=na_n$ gives

$$ \boxed{ a_n=\frac{1}{n}\sum_{d\mid n}\mu(d)p^{n/d} } $$

This is the standard formula for the number of monic irreducible degree-$n$ polynomials over $\mathbb{F}_p$. It also immediately explains several small cases:

$$ a_1=p~,\qquad a_2=\frac{p^2-p}{2}~,\qquad a_3=\frac{p^3-p}{3}~,\qquad a_4=\frac{p^4-p^2}{4}~. $$

6. Why $a_n$ is always positive

The formula is useful only if it really guarantees an irreducible polynomial in every degree. For $n=1$, $a_1=p>0$. For $n\ge2$,

$$ na_n =p^n+\sum_{\substack{d\mid n\\ d>1}}\mu(d)p^{n/d} \ge p^n-\sum_{\substack{d\mid n\\ d>1}}p^{n/d}~. $$

If $d>1$, then $n/d\le n/2$. The exponents $n/d$ appearing in the divisor sum are distinct positive integers, so

$$ \sum_{\substack{d\mid n\\ d>1}}p^{n/d} \le \sum_{j=1}^{\lfloor n/2\rfloor}p^j < p^n\qquad (p\ge2)~. $$

The last inequality follows from the geometric-series bound. Writing $m=\lfloor n/2\rfloor$, we have

$$ \sum_{j=1}^{m}p^j = \frac{p^{m+1}-p}{p-1} < p^{m+1} \le p^n~, $$

where the final inequality uses $m+1\le n$ for $n\ge2$. Hence $na_n>0$, and therefore

$$\boxed{a_n>0\quad\text{for every }n\ge1}$$

So for every prime $p$ and every positive integer $n$, at least one monic irreducible polynomial of degree $n$ exists over $\mathbb{F}_p$.

7. From irreducible polynomials to finite fields

Choose an irreducible polynomial $f(x)\in\mathbb{F}_p[x]$ of degree $n$. Since $(f)$ is then a maximal ideal,

$$\mathbb{F}_p[x]/(f)~,$$

is a field. Every residue class has a unique representative of degree less than $n$,

$$c_0+c_1x+\cdots+c_{n-1}x^{n-1}~,\qquad c_i\in\mathbb{F}_p~,$$

so there are exactly $p^n$ residue classes. We have therefore constructed a field of size $p^n$.

8. Example: irreducibles over $\mathbb{F}_2$

The first values of $a_n$ over the binary field are

$$a_1=2~,\qquad a_2=1~,\qquad a_3=2~,\qquad a_4=3~.$$

Representative lists are:

• Degree 1: $x$, $x+1$ ;
• Degree 2: $x^2+x+1$ ;
• Degree 3: $x^3+x+1$, $x^3+x^2+1$ ;
• Degree 4: $x^4+x+1$, $x^4+x^3+1$, $x^4+x^3+x^2+x+1$ .

Any one of the three degree-$4$ polynomials, for instance, may be used to construct a copy of $\mathbb{F}_{16}$.

9. A small computational check

The Möbius formula is easy to evaluate directly. The following dependency-free Python snippet computes $a_n$:

def divisors(n):
    return [d for d in range(1, n + 1) if n % d == 0]


def mobius(n):
    if n == 1:
        return 1

    prime_factors = 0
    d = 2
    m = n

    while d * d <= m:
        if m % d == 0:
            m //= d
            prime_factors += 1
            if m % d == 0:      # square factor
                return 0
            while m % d == 0:
                m //= d
        d += 1

    if m > 1:
        prime_factors += 1

    return -1 if prime_factors % 2 else 1


def irreducible_count(p, n):
    total = sum(mobius(d) * p ** (n // d) for d in divisors(n))
    return total // n


for n in range(1, 9):
    print(n, irreducible_count(2, n))

For $p=2$, this prints $2,1,2,3,6,9,18,30$ for degrees $1$ through $8$.

10. Wrap-up

The argument is a compact example of several areas of mathematics reinforcing one another. Unique factorization turns polynomial decomposition into a counting problem; generating functions turn that count into an Euler product; logarithms convert products into divisor sums; and Möbius inversion extracts the exact number of irreducibles. The final payoff is structural: irreducible polynomials provide the missing ingredient needed to construct every finite field.

There are several natural directions to continue from here: proving uniqueness of $\mathbb{F}_{p^n}$ up to isomorphism, studying the Frobenius automorphism, characterizing subfields of finite fields, or connecting irreducible polynomials with cyclic multiplicative groups and coding theory.

References

• T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976. See the discussion of the Möbius function and Möbius inversion.
• R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Cambridge University Press, 1997.

If you notice any errors or have suggestions, feel free to send me an email.