The Arithmetic of Polynomials Modulo p

In §§1,2, proofs are to be supplied by the reader, results under discussion are analogous to those in the NZM text, and the numbering is intended to emphasize the correspondence. One may view this unit as an introduction to finite fields, but in a very old-fashioned way, from the viewpoint of classical elementary number theory.

Throughout, p is a fixed prime. Suppose that f(x) = ∑ a_{i}x^{i} and g(x) = ∑ b_{i}x^{i} are two polynomials. We must distinguish between the following two assertions:

(I) a_{i} ≡ b_{i} (mod p) for all i;
(II) f(x) ≡ g(x) (mod p) for all integers x.

Of course (I) implies (II) but the converse is false (since for example we might have f(x) = x^{p} − x and g(x) = 0). To facilitate this distinction we adopt a notation that is consistent with modern algebra. We let F_{p} denote the field of residue classes modulo p, and F_{p}[x] the ring of polynomials whose coefficients are residue classes (mod p). We write f(x) = g(x), or more briefly f = g if (I) holds.

1. Divisibility and Factorization

The theory here is entirely analogous to the theory we have developed for the integers. The numbering below coincides with that in NZM, and the proofs are parallel. Hence, we hold these truths to be self-evident:

Definition 1.1. If f ∈ F_{p}[x] and g ∈ F_{p}[x] then we say that f divides g, and write f|g, if there is a polynomial m ∈ F_{p}[x] such that mf = g. We say that f and g are associates if there is a non-zero residue class c ∈ F_{p}^{×} such that cf = g.

Theorem 1.1. Suppose that a, b, c are polynomials in F_{p}[x]. Then (1) a|b implies that a|bc for any c ∈ F_{p}[x];

(2) a|b and b|c imply that a|c;

(3) a|b and a|c imply that a|(bu + cv) for any u, v ∈ F_{p}[x];

(4) If a|b then deg a ≤ deg b.

(5) a|b and b|a imply that a and b are associates.

(6) Suppose that m is a non-zero polynomial in F_{p}[x]. Then a|b if and only if ma|mb.

Theorem 1.2. (The division algorithm) Let a and b be polynomials in F_{p}[x] with a ≠ 0. Then there exist polynomials q and r in F_{p}[x] such that b = qa + r and deg r < deg a.

The remainder r may be 0 (the zero polynomial, all of whose coefficients are 0); we put deg 0 = −∞. Thus the identity deg ab = deg a + deg b holds even when one of the factors is 0.

Definition 1.2. Let a and b be polynomials in F_{p}[x]. We say that a polynomial d ∈ F_{p}[x] is a common divisor of a and b if d|a and d|b. If a ≠ 0 or b ≠ 0 then we say that g ∈ F_{p}[x] is a greatest common divisor of a and b if g is a common divisor of a and b and deg g is maximal among all common divisors of a and b. In this case we write g = (a, b).

Theorem 1.3. If g ∈ F_{p}[x] is a greatest common divisor of b and c then there exist polynomials u and v in F_{p}[x] such that g = bu + cv. Any two greatest common divisors of b and c are associates.

Theorem 1.4. The greatest common divisor g of two polynomials b and c in F_{p}[x] can be characterized in the following two ways: (1) Among non-zero polynomials of the form bu + cv where u and v are polynomials in F_{p}[x], g has minimal degree; (2) g is a common divisor of b and c that is divisible by every other common divisor.

Theorem 1.5. Given any polynomials b_{1}, b_{2}, …, b_{n} in F_{p}[x], not all zero, with greatest common divisor g, there exist polynomials u_{1}, u_{2}, …, u_{n} such that

g = (b_{1}, b_{2}, …, b_{n}) = ∑_{j=1}^{n} b_{j}u_{j}.

Among all non-zero polynomials of the form ∑_{j=1}^{n} b_{j}v_{j}, where the v_{j} are polynomials in F_{p}[x], g is one whose degree is minimal. All common divisors of b_{1}, b_{2}, …, b_{n} divide g, and any two greatest common divisors are associates.

Theorem 1.6. If a and b are polynomials in F_{p}[x], not both zero, and if m is a non-zero polynomial in F_{p}[x], then (ma, mb) = m(a, b).

Theorem 1.7. Suppose that a and b are polynomials in F_{p}[x], not both zero. If d is a non-zero polynomial in F_{p}[x] such that d|a and d|b, then

(\frac{a}{d}, \frac{b}{d}) = \frac{1}{d}(a, b).

In particular, if g = (a, b) then

(\frac{a}{g}, \frac{b}{g} ) = 1.

Theorem 1.8. Let a, b, and m be polynomials in F_{p}[x], at least two of them non-zero. If (a, m) = 1 and (b, m) = 1, then (ab, m) = 1.

Definition 1.3. Let a and b be polynomials in F_{p}[x]. We say that a and b are relatively prime if (a, b) = 1. We say that a_{1}, a_{2}, …, a_{n} are relatively prime if (a_{1}, a_{2}, …, a_{n}) = 1. We say that a_{1}, a_{2}, …, a_{n} are relatively prime in pairs if (a_{i}, a_{j}) = 1 for all i = 1, 2, …, n and all j = 1, 2, …, n with j ≠ i.

Theorem 1.9. Let a and b be polynomials in F_{p}[x], not both zero, and let x be any polynomial in F_{p}[x]. Let c be any non-zero residue class (mod p). Then (a, b) = (b, a) = (a, cb) = (a, b + ax).

Theorem 1.10. Suppose that a, b, and c are polynomials in F_{p}[x]. If c|ab and (b, c) = 1, then c|a.

Theorem 1.11. (The Euclidean Algorithm) Given polynomials b and c ≠ 0 in F_{p}[x], we make a repeated application of the division algorithm, Theorem 1.2, to obtain a series of equations

b = cq_{1} + r_{1},  0 < deg r_{1} < deg c,
c = r_{1}q_{2} + r_{2}  0 < deg r_{2} < deg r_{1},
r_{1} = r_{2}q_{3} + r_{3},  0 < deg r_{3} < deg r_{2},
⋮  ⋮
r_{j−2} = r_{j−1}q_{j} + r_{j}  0 < deg r_{j} < deg r_{j−1},
r_{j−1} = r_{j}q_{j+1}.

The greatest common divisor (b, c) of b and c is r_{j}, the last non-zero remainder in the division process. Values of u_{0} and v_{0} in (b, c) = bu_{0} + cv_{0} can be obtained by writing each r_{i} as a linear combination of b and c.

Definition 1.4. The polynomials a_{1}, a_{2}, …, a_{n} in F_{p}[x], all different from zero, have a common multiple b if a_{i}|b for all i = 1, 2, …, n. (Note that common multiples do exist; for example the product a_{1}a_{2} ⋯ a_{n} is one.) The least common multiple of the a_{i} is non-zero common multiple of minimal degree, and is denoted by [a_{1}, a_{2}, …, a_{n}].

Theorem 1.12. If b is a common multiple of the polynomials a_{1}, a_{2}, …, a_{n} in F_{p}[x] then [a_{1}, a_{2}, …, a_{n}]|b. This is the same thing as saying that if h = [a_{1}, a_{2}, …, a_{n}] then the common multiples of the a_{i} are precisely the polynomials of the form mh where m ranges over all polynomials in F_{p}[x].

Theorem 1.13. If m, a, and b are non-zero polynomials in F_{p}[x] then [ma, mb] = m[a, b]. Also, [a, b](a, b) = ab.

Definition 1.5. A polynomial f ∈ F_{p}[x] is called reducible if it can be written in the form f = ab where a and b are non-constant polynomials. If f has no divisor d satisfying 0 < deg d < deg f then f is irreducible.

Theorem 1.14. Every non-constant polynomial a ∈ F_{p}[x] can be written as a product of irreducible polynomials.

Theorem 1.15. Suppose that f, a, and b are non-zero polynomials in F_{p}[x]. If f is irreducible and f|ab then f|a or f|b. More generally, if f|a_{1}a_{2} ⋯ a_{n} then f|a_{i} for at least one i = 1, 2, …, n.

Theorem 1.16. (The Fundamental Theorem of Arithmetic) The factoring of a polynomial a ∈ F_{p}[x] into irreducible polynomials is unique apart from the ordering of the factors, and the choice of associates.

Suppose that a, b, c are polynomials in F_{p}[x] with factorizations

a = ∏_{f} f^{α(f)}  b = ∏_{f} f^{β(f)}  c = ∏_{f} f^{γ(f)}

where the polynomials f are irreducible. If ab = c then by Theorem 1.16 we deduce that α(f) + β(f) = γ(f) for all f. Hence a|c if and only if α(f) ≤ γ(f) for all irreducible polynomials f ∈ F_{p}[x]. Consequently, the greatest common divisor and least common multiple of a and b have factorizations

(a, b) = ∏_{f} f^{min(α(f),β(f))},  [a, b] = ∏_{f} f^{max(α(f),β(f))}.

Thus the identity of Theorem 1.6 is equivalent to the identity min(μ + α, μ + β) = μ + min(α, β), and the second identity in Theorem 1.13 is equivalent to the identity min(α, β)+ max(α, β) = α + β.

The results here do not depend on the fact that the ground field is the field F_{p} of residues modulo p. Thus in abstract algebra, one proves that if F is an arbitrary field then the polynomials F [x] with coefficients in F have a division algorithm, which yields a Euclidean algorithm, and hence unique factorization. Moreover, if I is an ideal in the ring F [x], then by Theorem 1.5 we know that I is principal; that is, there is a polynomial f∈F [x] such that I=(f). This gives rise to a quotient ring F [x]/(f), whose structure is also subject to investigation. In the case of F_{p}[x]/(f) we develop this in the next section, using the more number-theoretic language of congruences.

2. Congruences

Definition 2.1. Let m be a non-zero polynomial in F_{p}[x]. If a and b are polynomials in F_{p}[x] such that m|(a − b) then we say that a is congruent to b modulo m, and we write a ≡ b (mod m). If m ∤ (a − b) then we write a ≢ b (mod m).

Theorem 2.1. Let a, b, c, and d denote polynomials in F_{p}[x], and let f be a non-zero polynomial in F_{p}[x]. Then:

(1) a ≡ b (mod f), b ≡ a (mod f), and a − b ≡ 0 (mod f) are equivalent statements;

(2) If a ≡ b (mod f) and b ≡ c (mod f) then a ≡ c (mod f);

(3) If a ≡ b (mod f) and c ≡ d (mod f) then a + c ≡ b + d (mod f);

(4) If a ≡ b (mod f) and c ≡ d (mod f) then ac ≡ bd (mod f);

(5) If a ≡ b (mod f) and d|f then a ≡ b (mod d);

(6) If a ≡ b (mod f) then ac ≡ bc (mod fc).

Theorem 2.2. Suppose that a, b, and f are polynomials in F_{p}[x]. If P is a polynomial in F_{p}[x] and a ≡ b (mod f) then P (a) ≡ P (b) (mod f).

Theorem 2.3. Suppose that a, u, v, and f are polynomials in F_{p}[x]. Then (1) au ≡ av (mod f) if and only if u ≡ v (mod \frac{f}{(a,f)}).

(2) If au ≡ av (mod f) and (a, f) = 1 then u ≡ v (mod f).

(3) u ≡ v (mod f_{i}) for i = 1, 2, …, r if and only if u ≡ v (mod [f_{1}, f_{2}, …, f_{r}]).

Definition 2.2. Suppose that u, v, and f are polynomials in F_{p}[x]. If u ≡ v (mod f) then we say that v is a residue of u modulo f. A set u_{1}, u_{2}, …, u_{k} is called a complete residue system modulo f if for every polynomial v in F_{p}[x] there is one and only one u_{i} such that v ≡ u_{i} (mod f).

The set of polynomials of degree less than the degree of f form a complete system of residues modulo f. Hence the number of residues in a complete system is k = p^{deg f}.

Theorem 2.4. Suppose that b, c, and f are polynomials in F_{p}[x]. If b ≡ c (mod f) then (b, f) = (c, f).

Definition 2.3. Let f be a polynomial in F_{p}[x]. A reduced residue system modulo f is a set of polynomials r_{1}, r_{2}, …, r_{k} such that (r_{i}, f) = 1 and r_{i} ≢ r_{j} (mod f) if i ≠ j, and such that if u is a polynomial such that (u, f) = 1, then u ≡ r_{i} (mod f) for exactly one value of i.

If f is irreducible in F_{p}[x], then all polynomials of degree less than that of f are relatively prime to f, except for the zero polynomial. Hence in this case the number of polynomials in a system of reduced residues is p^{deg f} − 1.

Theorem 2.6. Suppose that a and f are polynomials in F_{p}[x], and that (a, f) = 1. Let r_{1}, r_{2}, …, r_{k} be a complete, or reduced, system of residues modulo f. Then ar_{1}, ar_{2}, …, ar_{k} is a complete, or reduced system of residues, respectively, modulo f.

Theorem 2.7. Let f be an irreducible polynomial in F_{p}[x] of degree n. If f ∤ a then a^{p^{n}−1} ≡ 1 (mod f).

Theorem 2.8. Let f be a polynomial in F_{p}[x], and let ϕ(f) be the number of polynomials in a reduced system of residues modulo f. If (a, f) = 1 then a^{ϕ(f)} ≡ 1 (mod f).

Theorem 2.9. Let a and f be polynomials in F_{p}[x]. If (a, f) = 1 then there is a polynomial u such that au ≡ 1 (mod f). Any two such u are congruent (mod f). If (a, f) is a polynomial of degree > 0 then there is no such u.

Theorem 2.10. Let u and f be polynomials in F_{p}[x], and suppose that f is irreducible. Then u^{2} ≡ 1 (mod f) if and only if u ≡ ±1 (mod f).

Theorem 2.11. Let f be an irreducible polynomial in F_{p}[x], and let r_{1}, r_{2}, …, r_{k} be a system of reduced residues modulo f. Then ∏_{i=1}^{k} r_{i} ≡ −1 (mod f).

Definition 2.4. Let f be a polynomial in F_{p}[x], and let r_{1}, r_{2}, …, r_{k} be a complete system of residues modulo f. Let P (z) be a polynomial whose coefficients are in F_{p}[x]. The number of solutions of the congruence P (u) ≡ 0 (mod f) is the number of i for which P (r_{i}) ≡ 0 (mod f).

Theorem 2.18. (The Chinese Remainder Theorem) Let f_{1}, f_{2}, …, f_{r} be non-zero polynomials in F_{p}[x], and suppose that the f_{i} are relatively prime in pairs. Let a_{2}, a_{2}, …, a_{r} be any polynomials in F_{p}[x]. Then there is a polynomial u such that u ≡ a_{i} (mod f_{i}) for i = 1, 2, … r. If f = f_{1}f_{2} ⋯ r_{r} then any two such u are congruent modulo f.

Theorem 2.19. If a is a polynomial in F_{p}[x] let ϕ(a) be the number of polynomials in a reduced system of residues modulo a. If (a, b) = 1 then ϕ(ab) = ϕ(a)ϕ(b). If a = ∏_{f} f^{α} is the factorization of a into irreducible polynomials, then ϕ(a) = ∏_{f} p^{n(α−1)}(p^{n} − 1) where n = n_{f} = deg f.

Theorem 2.20. Let a and b denote polynomials in F_{p}[x], and let P (z) be a polynomial whose coefficients are in F_{p}[x]. Let N_{P} (a) denote the number of solutions of the congruence P (u) ≡ 0 (mod a). If (a, b) = 1 then N_{P} (ab) = N_{P} (a)N_{P} (b).

Theorem 2.26. Let f be an irreducible polynomial in F_{p}[x], and let P (z) be a polynomial of degree k whose coefficients are in F_{p}[x]. Then the congruence P (u) ≡ 0 (mod f) has at most k solutions.

Theorem 2.29. Let f be an irreducible polynomial in F_{p}[x], and let n = deg f. Suppose that P (z) be a polynomial of degree k whose coefficients coefficients are in F_{p}[x]. Then the congruence P (u) ≡ 0 (mod f) has exactly k solutions if and only if there is a polynomial Q(z) whose coefficients are in F_{p}[x] such that u^{p^{n}} − u ≡ P (u)Q(u) (mod f) for all polynomials u ∈ F_{p}[x].

Corollary 2.30. Let f be an irreducible polynomial of degree n in F_{p}[x]. If d|(p^{n} −1) then the congruence u^{d} ≡ 1 (mod f) has exactly d solutions.

Definition 2.6. Let f and a be any two polynomials in F_{p}[x], and suppose that (a, f) = 1. Let h be the least positive integer such that a^{h} ≡ 1 (mod f). We say that the order of a modulo f is h, or that a belongs to the exponent h modulo f.

Lemma 2.31. Let a and f be polynomials in F_{p}[x]. If a has order h modulo f then a^{k} ≡ 1 (mod f) if and only if h|k.

Corollary 2.32. Let a and f be polynomials in F_{p}[x]. If (a, f) = 1 then the order of a modulo f divides p^{n} − 1, where n = deg f.

Lemma 2.33. Let a and f be polynomials in F_{p}[x]. If a has order h modulo f then a^{k} has order h/(h, k) modulo f.

Lemma 2.34. Let a, b and f be polynomials in F_{p}[x]. If a has order h modulo f and b has order k modulo f, and (h, k) = 1, then ab has order hk modulo f.

Definition 2.7. Let f be a polynomial in F_{p}[x]. If g belongs to the exponent ϕ(f) then g is a primitive root modulo f.

Lemma 2.35. Let f be an irreducible polynomial of degree n in F_{p}[x]. If q is prime and q^{α}|(p^{n} − 1) where α ≥ 1, then there are precisely q^{α} − q^{α−1} residue classes modulo f of order q^{α}.

Theorem 2.36. If f is an irreducible polynomial of degree n in F_{p}[x] then there exist exactly ϕ(p^{n} − 1) primitive roots modulo f.

Theorem 2.37. Let f be an irreducible polynomial of degree n in F_{p}[x]. If (a, f) = 1 then the congruence u^{k} ≡ a (mod f) has (k, p^{n} − 1) solutions or no solution, according as

a^{(p^{n}−1)/(k,p^{n}−1)} ≡ 1 (mod f),

or not.

The correspondence with numbering in NZM ends at this point.

Example 1. Let p = 2. Then we have the polynomials 0, 1, x, x + 1, x^{2}, x^{2} + 1, x^{2} + x, x^{2} + x + 1, . . .. If a quadratic polynomial is reducible then it is the product of two linear polynomials. We note that x^{2} = x^{2}, x(x + 1) = x^{2} + x, and that (x + 1)^{2} = x^{2} + 1. Thus three of the four quadratic polynomials available is reducible, but f(x) = x^{2} + x + 1 is irreducible. A complete system of residues modulo f is given by r_{0} = 0, r_{1} = 1, r_{2} = x, r_{3} = x + 1. By direct calculation we find that

\begin{matrix}+ & r_{0} & r_{1} & r_{2} & r_{3} \\ r_{0} & r_{0} & r_{1} & r_{2} & r_{3} \\ r_{1} & r_{1} & r_{0} & r_{3} & r_{2} \\ r_{2} & r_{2} & r_{3} & r_{0} & r_{1} \\ r_{3} & r_{3} & r_{2} & r_{1} & r_{0} \end{matrix}  \begin{matrix}× & r_{0} & r_{1} & r_{2} & r_{3} \\ r_{0} & r_{0} & r_{0} & r_{0} & r_{0} \\ r_{1} & r_{0} & r_{1} & r_{2} & r_{3} \\ r_{2} & r_{0} & r_{2} & r_{3} & r_{1} \\ r_{3} & r_{0} & r_{3} & r_{1} & r_{2} \end{matrix}

Here we see that r_{2} and r_{3} have order 3 (mod f), so they are the primitive roots in this case.

Suppose that f is an irreducible polynomial of degree n in F_{p}[x]. We have shown that polynomials modulo f form a field, and that the multiplicative group of non-zero elements is cyclic. It is also easy to see that the additive group is isomorphic to (C_{p})^{n}. More generally, if F is a finite field then by the pigeon-hole principle there is a positive integer n such that n=0. The least such positive integer is called the characteristic of the field. It is easy to see that if the characteristic of a field is finite, then it must be a prime number. The fields constructed above have p^{n} elements and characteristic p. It can also be shown that the number of elements in a finite field of characteristic p must be p^{n} for some n. The proof we have given that the multiplicative group of non-zero elements is cyclic generalizes to arbitrary finite fields. In §4 below we show that for every prime number p and every positive integer n there is at least one irreducible polynomial of degree n in F_{p}[x]. Hence there is a field of p^{n} elements. Finally, it can be shown that any two finite fields of the same size are isomorphic. Hence there is essentially only one field of size p^{n}. Note, however, that when n>1 the field of p^{n} elements is not the same as the ring of integers modulo p^{n}, which is not a field.

3. Derivatives

Definition 3.1. If f(x) = ∑_{i=0}^{n} a_{i}x^{i} is a polynomial, then the derivative of f(x) is the polynomial f′(x) = ∑_{i=1}^{n} ia_{i}x^{i−1}.

It is easy to verify that (f(x) + g(x))′ = f′(x) + g′(x), that (cf(x))′ = cf′(x), that (f(x)g(x))′ = f′(x)g(x) + f(x)g′(x), and hence that (f(x)^{k})′ = kf(x)^{k−1}f′(x). Suppose now that a and f are polynomials in F_{p}[x], that f is irreducible, and that f divides a exactly to the power α > 0, say a = f^{α}g. Then a′ = αf^{α−1}f′ + f^{α}g′, so that f divides a′ to at least the power α − 1. (If p ∤ α then the power is exactly α − 1, but if p|α then the power is at least α.) Hence (a, a′) = 1 if and only if a is square-free.

4. Further factorizations

Theorem 4.1. If d and n are positive integers and d|n then there is a polynomial u(x) with integral coefficients such that (x^{d} − 1)u(x) = x^{n} − 1.

Proof. Put u(x) = x^{n−d} + x^{n−2d} + ⋯ + x^{d} + 1.

Corollary 4.2. If a is an integer and d and n are positive integers such that d|n, then (a^{d} − 1)|(a^{n} − 1).

Theorem 4.3. Let m and n be positive integers, and suppose that (m, n) = g. Then there exist polynomials u(x) and v(x) with integral coefficients such that

(x^{m} − 1)u(x) + (x^{n} − 1)v(x) = x^{g} − 1.

Proof. Suppose that m ≥ n, and write m = q_{1}n + r_{1} where 0 ≤ r_{1} < n. Then

x^{r_{1}} − 1 = (x^{m} − 1) − (x^{q_{1}n} − 1)x^{r_{1}} = (x^{m} − 1)u_{1}(x) + (x^{n} − 1)v_{1}(x),

say. Next write n = q_{2}r_{1} + r_{2} where 0 ≤ r_{2} < r_{1}, so that

x^{r_{2}} − 1 = (x^{n} − 1) − (x^{q_{2}r_{1}} − 1)x^{r_{2}} = (x^{m} − 1)u_{2}(x) + (x^{n} − 1)v_{2}(x).

By continuing with the Euclidean algorithm, we eventually reach the last non-zero remainder r_{j}, and

x^{r_{j}} − 1 = (x^{m} − 1)u_{j}(x) + (x^{n} − 1)v_{j}(x).

Since r_{j} = g, this gives the result.

The calculation just completed is unusual in that each remainder polynomial is monic, so that when it is used as a divisor, the resulting quotient still has integral coefficients. Normally, if p(x) and q(x) are relatively prime polynomials with integral coefficients and one writes p(x)u(x)+q(x)v(x)=1, the coefficients of u(x) and v(x) are rational numbers. One can multiply by the least common denominator of these coefficients to obtain an identity of the form p(x)u(x)+q(x)v(x)=c; the least integer c that can be so expressed is of considerable significance and is called the resultant of the polynomials. Hence from the above we see that if (m,n)=1 then the resultant of x^{m}−1 and x^{n}−1 is 1.

Corollary 4.4. Let m and n be positive integers, and put g = (m, n). Then for any integer a, (a^{m} − 1, a^{n} − 1) = a^{g} − 1.

Proof. Let G = (a^{m} − 1, a^{n} − 1). Since u(a) and v(a) are integers it follows from Theorem 4.3 that G|(a^{g} − 1). On the other hand, by Corollary 4.2 we see that a^{g} − 1 divides both a^{m} − 1 and a^{n} − 1. Hence (a^{g} − 1)|G, so that G = a^{g} − 1.

Theorem 4.5. Let f be a polynomial in F_{p}[x]. Then f(x)^{p} = f(x^{p}).

Proof. Let u and v be any two polynomials in F_{p}[x]. Then (u + v)^{p} = u^{p} + v^{p} since p|({p \atop k} ) for 0 < k < p. Hence by induction, (u_{1} + u_{2} + ⋯ + u_{n})^{p} = u_{1}^{p} + u_{2}^{p} + ⋯ + u_{n}^{p}. Thus if f(x) = ∑_{i} a_{i}x^{i} then f(x)^{p} = ∑_{i}(a_{i}x^{i})^{p}. But a_{i}^{p} ≡ a_{i} (mod p), so this is ∑ a_{i}x^{ip} = f(x^{p}).

Theorem 4.6. (Gauss) Let ℱ_{n} denote the set of all monic irreducible polynomials of degree n in F_{p}[x]. Then for any positive integer n,

(1)  x^{p^{n}} − x = ∏_{d|n} ∏_{f∈ℱ_{d}} f(x).

The case n = 1 of this is already in §2.7 of NZM.

Proof. Let h(x) = x^{p^{n}} − x ∈ F_{p}[x]. Then h′(x) = −1. Hence (h, h′) = 1, and so h is square-free. Thus to determine the factorization of g it is enough to determine which irreducible polynomials divide it.

Suppose that d|n, and that f ∈ ℱ_{d}. Then (f, x) = 1 unless d = 1 and f(x) = x, in which case f|h. Otherwise it follows by Theorem 2.8 that x^{p^{d}−1} ≡ 1 (mod f). That is, f|(x^{p^{d}−1} − 1). But (p^{d} − 1)|(p^{n} − 1) by Corollary 4.2, and hence (x^{p^{d}−1} − 1)|(x^{p^{n}−1} − 1) by Theorem 4.1. Hence the right hand side displayed above divides the left hand side.

To complete the proof it suffices to show that if f is an irreducible monic polynomial of degree m that divides x^{p^{n}} − x then m|n. If f(x) = x then m = 1, and we are done, since 1|n. Otherwise, (f, x) = 1, so from f|(x^{p^{n}} − x) it follows by Theorem 1.10 that f|(x^{p^{n}−1} − 1). We also know, by Theorem 2.7, that f|(x^{p^{m}−1} − 1). Then by Theorem 4.3 it follows that f|(x^{p^{d}−1} − 1), where d = (m, n). That is, x^{p^{d}−1} ≡ 1 (mod f), which implies that x^{p^{d}} ≡ x (mod f). Let g(x) be an arbitrary polynomial in F_{p}[x]. By d applications of Theorem 4.5 we see that g(x)^{p^{d}} = g(x^{p^{d}}). But this is ≡ g(x) (mod f) by Theorem 2.2. Thus g(x)^{p^{d}} ≡ g(x) (mod f). If (g, f) = 1 then we may cancel g from both sides, to see that g(x)^{p^{d}−1} ≡ 1 (mod f). Now suppose that g is a primitive root of f. Then the order of g modulo f is p^{m} − 1, and so we deduce that d ≥ m. But d is a divisor of m, so it follows that d = m. As d is also a divisor of n we conclude that m|n, and the proof is complete.

Corollary 4.7. For each n ≥ 1, there is at least on irreducible polynomial in F_{p}[x] of degree n.

Proof. By applying the identity deg ab = deg a + deg b in (1), we deduce that

(2)  p^{n} = ∑_{d|n} d card ℱ_{d}.

The Arithmetic of Polynomials Modulo p

By discarding the (non-negative) contribution of the terms for d < n, we deduce that

(3)  card ℱ_{n} ≤ \frac{p^{n}}{n}

for all n. By (2) we see that

n card ℱ_{n} = p^{n} − ∑_{\begin{matrix}d|n \\ d<n \end{matrix}} d card ℱ_{d}

which by (3) is

≥ p^{n} − ∑_{\begin{matrix}d|n \\ d<n \end{matrix}} p^{d}

≥ p^{n} − ∑_{1≤d≤[n/2]} p^{d}

≥ p^{n} − \frac{p^{[n/2]+1} − 1}{p − 1}.

Since p ≥ 2, this is

≥ p^{n} − p^{[n/2]+1} + 1.

But [n/2] + 1 ≤ n for n = 1, 2, 3, …, so the above is ≥ 1. Corollary 4.8. The number of monic irreducible polynomials of degree n in F_{p}[x] is exactly

\frac{1}{n} ∑_{d|n} μ(d)p^{n/d}.

Proof. Apply the Möbius inversion formula to the identity (1).

It is somewhat curious that the sum above should always be divisible by n. Since p might lie in any reduced residue class modulo n, this suggests the first exercise below. In the second exercise we recover (2) without needing so much of the theory.

EXERCISES

1. Show (by an argument independent of the present context) that if (a, n) = 1, then

∑_{d|n} μ(d)a^{n/d} ≡ 0 (mod n).

2. (a) Let n_{k} denote the total number of monic polynomials of degree k in 𝔽_{p}[x]. Show that n_{k} = p^{k}.

(b) Let P_{1}, P_{2}, … be the irreducible monic polynomials in 𝔽_{p}[x], listed in some (arbitrary) order. Show that

∏_{r=1}^{∞} (1 + z^{deg P_{r}} + z^{2 deg P_{r}} + z^{3 deg P_{r}} + ⋯) = 1 + pz + p^{2}z^{2} + p^{3}z^{3} + ⋯

for |z| < 1/p.

(c) Let g_{k} denote the number of irreducible monic polynomials of degree k in 𝔽_{p}[x]. Show that

∏_{k=1}^{∞} (1 − z^{k})^{−g_{k}} = (1 − pz)^{−1} (|z| < 1/p).

(d) Take logarithmic derivatives to show that

∑_{k=1}^{∞} kg_{k} \frac{z^{k−1}}{1 − z^{k}} = \frac{p}{1 − pz} (|z| < 1/p).

(e) Show that

∑_{k=1}^{∞} kg_{k} ∑_{m=1}^{∞} z^{mk} = ∑_{n=1}^{∞} p^{n}z^{n} (|z| < 1/p).

(f) Deduce that

∑_{k|n} kg_{k} = p^{n}

for all positive integers n.

(g) (Gauss) Use the Möbius inversion formula to show that

g_{n} = \frac{1}{n} ∑_{k|n} μ(k)p^{n/k}

for all positive integers n.

(h) Use (f) (not (g)) to show that

\frac{p^{n}}{n} − \frac{2p^{n/2}}{n} ≤ g_{n} ≤ \frac{p^{n}}{n} .

(i) If a monic polynomial of degree n is chosen at random from 𝔽_{p}[x], about how likely is it that it is irreducible? (Assume that p and/or n is large.)

(j) Show that g_{n} > 0 for all p and all n ≥ 1. (If P ∈ 𝔽_{p}[x] is irreducible and has degree n, then the quotient ring 𝔽_{p}[x]/(P) is a field of p^{n} elements. Thus we have proved that there is such a field, for each prime p and integer n ≥ 1. It may be further shown that the order of a finite field is necessarily a primepower, and that any two finite fields of the same order are isomorphic. Hence the field of order p^{n}, whose existence we have proved, is essentially unique.)

3. (E. Berlekamp) Let p be a prime number. We recall that polynomials in a single variable (mod p) factor uniquely into irreducible polynomials. Thus a monic polynomial f(x) can be expressed uniquely (mod p) in the form g(x)h(x)^{2} where g(x) is squarefree (mod p) and both g and h are monic. Let s_{n} denote the number of monic squarefree polynomials (mod p) of degree n. Show that

( ∑_{k=0}^{∞} s_{k}z^{k})( ∑_{m=0}^{∞} p^{m}z^{2m}) = ∑_{n=0}^{∞} p^{n}z^{n}

for |z| < 1/p. Deduce that

∑_{k=0}^{∞} s_{k}z^{k} = \frac{1 − pz^{2}}{1 − pz} ,

and hence that s_{0} = 1, s_{1} = p, and that s_{k} = p^{k}(1 − 1/p) for all k ≥ 2.