back to the main writeup

Appendix: Existence of irreducible polynomials over the prime fields

This is an appendix to my writeup in finite field. It contains a proof that there exist irreducible polynomials of every degree over every prime field. References to numbered theorems and corollaries are references to my finite field writeup.

This writeup is the small print, for the specialist. I could not simplify the proof presented here. I therefore chose to write in a laconic mathematical style in stark contrast with the style in finite field.

The proof of Technical Lemma 1 begins with some lemmata of its own.

Lemma 1: Over any field, the polynomial xd - 1 divides the polynomial xn - 1 if and only if d divides n.

Proof: By the division algorithm, write n = dk + r with 0 ≤ r < d. Then we can express the quotient of xn - 1 by xd - 1 as

     xn - 1       xdk - 1     xr  - 1
     ------  = xr-------  +  --------   (1)
     xd - 1       xd - 1      xd - 1

Now, the polynomial xdk - 1 factors as (xd - 1)((xd)(k - 1) + (xd)(k - 2) + ··· + xd + 1), so the left term in the right-hand side of (1) is a polynomial. Since r < d, the only way that the entire right-hand side of (1) can be a polynomial is if r = 0. ♦

There is an immediate corollary of interest.

Corollary 1.1: The polynomial xpd - x divides xpn - x if and only if d divides n.

Proof: Dividing through by x we see that the proposition is true if and only xpd - 1 - 1 divides xpn - 1 - 1. By two successive applications of Lemma 1, we see this to be true if and only d divides n. ♦

The next lemma gives an interesting characterisation of the polynomial xq - x over a finite field of characteristic p when q = pn. It is interesting in its own right.

Lemma 2: Let q = pn be a power of a prime. Let fd(x) denote the product of all polynomials irreducible over Z/p of degree d. Then over Z/p,

xq - x = ∏d|n fd(x),

where the product is taken over all divisors d of n.

Proof: If an irreducible of degree d exists, then so does Fpd. Thus by Theorem 9, we already know that for any integer d, an irreducible of degree d divides xpd - x. Thus by Corollary 1.1 it follows that an irreducible of degree d divides xq - x if d divides n.

Thus it remains to show that xq - x has no repeated factors and that nothing else divides xq - x, that is, that if an irreducible polynomial of degree d divides xq - x, then d divides n.

To prove that xq - x has no repeated factors, suppose otherwise and xq - x = (f(x))2g(x). By formal differentiation in characteristic p, this implies that

-1 = 2f(x)f'(x)g(x) + (f(x))2g'(x),

which can only happen if f(x) divides 1. Thus xq - x has no repeated nontrivial factors.

Now suppose that xq - x = f(x)g(x) with f(x) irreducible of degree d. We must show that d divides n. Let α be a root of f(x) in Fpd. By Fermat's Little Theorem for finite fields, (a finite field of degree d exists by assumption that f(x) exists), αpd = α, and because f(x) is a factor of xq - x, we also see that αq = α. Let t be any element of the field obtained by adjoining α to Z/p. Again by Fermat's Little Theorem we know that tpd = t, but also by Kronecker's construction we know that we can write t as

t = ad-1αd-1 + ad-2αd-2 + ··· + a1α + a0,

where the ai are elements of Z/p. Because the Frobenius automorphism is an automorphism that fixes the prime field, we can apply it n times and raise both sides to the qth power to see that

tq = (ad-1αd-1 + ad-2αd-2 + ··· + a1α + a0)q,
= ad-1αq(d-1) + ad-2αq(d-2) + ··· + a1αq + a0,
=ad-1αd-1 + ad-2αd-2 + ··· + a1α + a0 = t,

where we have used the previously mentioned fact that αq = α in the last step. Because tq = t and t was arbitrary, every factor of xpd - x is also a factor of xq - x, so xpd - x divides xq - x. By Corollary 1.1, this can only happen if d divides n. ♦

The proof can now be completed by counting degrees and invoking the Mobius inversion formula.

Technical Lemma 1: There exists an irreducible polynomial of every degree over every prime field.

Proof: Let Nd denote the number of irreducible polynomials of degree d over Z/p. By equating degrees on both sides of the equation in Lemma 2, we see that

pn = ∑d|n dNd,

where the sum is taken over all d that divide n. By Mobius inversion, we can rewrite this as

Nn = (1/n)∑d|n μ(n/d)pd,

where μ denotes the Mobius function of classical number theory. By looking at the expression for Nn, we see that it must be positive, as it has the term pn, and then plus, minus, or zero lower powers of p. Since the number of irreducible polynomials of degree n over Z/p is positive, there must be at least one. ♦

back to the main writeup