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