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
*x*^{d} - 1 divides the polynomial
*x*^{n} - 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 *x*^{n} - 1 by
*x*^{d} - 1 as

*x*^{n} - 1 *x*^{dk} - 1 *x*^{r} - 1
------ = *x*^{r}------- + -------- (1)
*x*^{d} - 1 *x*^{d} - 1 *x*^{d} - 1

Now, the polynomial *x*^{dk} - 1 factors as
(*x*^{d} - 1)((*x*^{d})^{(k
- 1)}
+ (*x*^{d})^{(k - 2)} +
··· + *x*^{d} + 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
*x*^{pd} - *x* divides
*x*^{pn} - *x* if and only if
*d* divides *n*.
*Proof:* Dividing through by *x* we see that the
proposition is true if and only
*x*^{pd - 1} - 1 divides
*x*^{pn - 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 *x*^{q} - *x* over a finite field of
characteristic *p* when *q* = *p*^{n}. It
is interesting in its own right.

**Lemma 2:** Let *q* = *p*^{n} be a
power of a prime. Let *f*_{d}(*x*) denote the
product of all polynomials irreducible over **Z**/*p* of degree *d*.
Then over **Z**/*p*,
*x*^{q} - *x* = ∏_{d|n}
*f*_{d}(*x*),

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

*Proof:* If an irreducible of degree *d* exists, then so does **F**_{pd}. Thus by Theorem 9, we already know that for any integer *d*, an irreducible of degree *d* divides *x*^{pd} - *x*. Thus by
Corollary 1.1 it follows that an irreducible of degree *d*
divides *x*^{q} - *x* if *d* divides
*n*.

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

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

-1 =
2*f*(*x*)*f*'(*x*)*g*(*x*) +
(*f*(*x*))^{2}*g*'(*x*),

which can only happen if *f*(*x*) divides 1. Thus
*x*^{q} - *x* has no repeated nontrivial factors.

Now suppose that *x*^{q} - *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
**F**_{pd}. 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 *x*^{q} -
*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 *t*^{pd} = *t*, but also by Kronecker's construction we know that we can write *t* as

*t* =
*a*_{d-1}α^{d-1} +
*a*_{d-2}α^{d-2} +
···
+
*a*_{1}α +
*a*_{0},

where the *a*_{i} 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 *q*th power to see that

*t*^{q} =
(*a*_{d-1}α^{d-1} +
*a*_{d-2}α^{d-2} +
···
+
*a*_{1}α +
*a*_{0})^{q},

=
*a*_{d-1}α^{q(d-1)} +
*a*_{d-2}α^{q(d-2)} +
···
+
*a*_{1}α^{q} +
*a*_{0},

=*a*_{d-1}α^{d-1} +
*a*_{d-2}α^{d-2} +
···
+
*a*_{1}α +
*a*_{0}
= *t*,

where we have used the previously mentioned fact that
α^{q} = α in the last step. Because
*t*^{q} = *t* and *t* was arbitrary,
every factor of *x*^{pd} - *x* is
also a factor of *x*^{q} - *x*, so
*x*^{pd} - *x* divides
*x*^{q} - *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 *N*_{d} 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

*p*^{n} = ∑_{d|n}
*dN*_{d},

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

*N*_{n} = (1/n)∑_{d|n}
μ(*n*/*d*)*p*^{d},

where μ denotes the Mobius function of classical number
theory. By looking at the expression for *N*_{n}, we
see that it must be positive, as it has the term
*p*^{n}, 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