TAOCP 4.6.2 Exercise 16

Section 4.6.2: Factorization of Polynomials

Exercise 16. [M30] (Finite fields.) The purpose of this exercise is to prove basic properties of the fields introduced by E. Galois in 1830.

a) Given that $f(x)$ is an irreducible polynomial modulo a prime $p$, of degree $n$, prove that the $p^n$ polynomials of degree less than $n$ form a field under arithmetic modulo $f(x)$ and $p$. [Note: The existence of irreducible polynomials of each degree is proved in exercise 4; therefore fields with $p^n$ elements exist for all primes $p$ and all $n \ge 1$.]

b) Show that any field with $p^n$ elements has a "primitive root" element $\xi$ such that the elements of the field are ${0, 1, \xi, \xi^2, \ldots, \xi^{p^n - 2}}$. [Hint: Exercise 3.2.1.2–16 provides a proof in the special case $n = 1$.]

c) If $f(x)$ is an irreducible polynomial modulo $p$, of degree $n$, prove that $x^{p^n} - x$ is divisible by $f(x)$ if and only if $m$ is a multiple of $n$. (It follows that we can test irreducibility rather quickly: A given $n$th degree polynomial $f(x)$ is irreducible modulo $p$ if and only if $x^{p^n} - x$ is divisible by $f(x)$ and $x^{p^{n/q}} - x \not\perp f(x)$ for all primes $q$ that divide $n$.)

Verified: no
Solve time: 2m45s

---

Setup

Let $p$ be a prime, and let $f(x)$ be an irreducible polynomial modulo $p$ of degree $n$.

Denote by

$F={,a_{n-1}x^{n-1}+\cdots+a_1x+a_0 : a_i\in{0,1,\ldots,p-1},}.$

Arithmetic in $F$ is performed modulo both $f(x)$ and $p$.

Part (a) asks us to prove that $F$ is a field.

Part (b) asks us to prove that every field with $p^n$ elements contains an element $\xi$ whose nonzero powers exhaust all nonzero elements of the field.

Part (c) asks us to determine when an irreducible polynomial $f(x)$ of degree $n$ divides $x^{p^m}-x$.

Solution

(a)

The set $F$ contains exactly $p^n$ polynomials, since each of the $n$ coefficients may be chosen independently from $p$ possibilities.

Addition and multiplication modulo $f(x)$ and $p$ are well defined. The zero polynomial is the additive identity, and the constant polynomial $1$ is the multiplicative identity.

The distributive, associative, and commutative laws hold because they hold for ordinary polynomial arithmetic and are preserved by reduction modulo $f(x)$ and $p$.

Only the existence of multiplicative inverses for nonzero elements remains to be proved.

Let $g(x)\in F$ be nonzero. Since $\deg g<n=\deg f$ and $f$ is irreducible, $f$ cannot divide $g$. Hence

$\gcd(f,g)=1.$

By the polynomial Euclidean algorithm, there exist polynomials $a(x)$ and $b(x)$ such that

$a(x)f(x)+b(x)g(x)=1.$

Reducing modulo $f(x)$ gives

$b(x)g(x)\equiv 1 \pmod{f(x)}.$

Therefore the residue class represented by $b(x)$ is a multiplicative inverse of $g(x)$.

Every nonzero element of $F$ is therefore invertible. Hence $F$ is a field with $p^n$ elements.

(b)

Let $K$ be any field with $p^n$ elements. Its nonzero elements form a finite multiplicative group

$K^\times=K\setminus{0},$

of order

$|K^\times|=p^n-1.$

Let $m$ be the maximum order of an element of $K^\times$. Every element $a\in K^\times$ satisfies

$a^m=1,$

because the order of $a$ divides $m$.

Consequently every element of $K^\times$ is a root of the polynomial

$x^m-1.$

Since a polynomial of degree $m$ over a field has at most $m$ roots,

$p^n-1=|K^\times|\le m.$

On the other hand, the order of every element of $K^\times$ divides the group order $p^n-1$, by Lagrange's theorem. Hence

$m\le p^n-1.$

Therefore

$m=p^n-1.$

An element $\xi\in K^\times$ of order $m$ exists by definition of $m$, and its order is

$\operatorname{ord}(\xi)=p^n-1.$

The powers

$1,\xi,\xi^2,\ldots,\xi^{p^n-2}$

are distinct and constitute all $p^n-1$ nonzero elements of $K$. Thus

$K={0,1,\xi,\xi^2,\ldots,\xi^{p^n-2}}.$

Hence $\xi$ is a primitive root of the field.

(c)

Let $K$ be the field obtained in part (a), consisting of residues modulo $f(x)$ and $p$. Since $\deg f=n$, the field $K$ has $p^n$ elements.

First suppose that $n\mid m$.

Every nonzero element $a\in K$ satisfies

$a^{p^n-1}=1,$

because the multiplicative group of $K$ has order $p^n-1$. Hence

$a^{p^n}=a.$

Since $n\mid m$, write $m=kn$. Repeated application of the map $a\mapsto a^{p^n}$ yields

$a^{p^m}=a.$

Thus every element of $K$ is a root of

$x^{p^m}-x.$

In particular, the residue class of $x$ modulo $f(x)$ satisfies this equation, so

$x^{p^m}-x\equiv0\pmod{f(x)}.$

Therefore $f(x)$ divides $x^{p^m}-x$.

Conversely, suppose that

$f(x)\mid x^{p^m}-x.$

Let $\alpha$ denote the residue class of $x$ in $K$. Then

$\alpha^{p^m}=\alpha.$

The map

$\varphi(a)=a^p$

is an automorphism of $K$. Its $m$th iterate fixes $\alpha$:

$\varphi^m(\alpha)=\alpha.$

Since $\alpha$ generates $K$ over $\mathbf F_p$ by construction, $\varphi^m$ fixes every element of $K$.

Let $\xi$ be a primitive root of $K$, as in part (b). Then

$\xi^{p^m}=\xi,$

hence

$\xi^{p^m-1}=1.$

Since $\xi$ has order $p^n-1$,

$p^n-1\mid p^m-1.$

For positive integers $r$ and $s$,

$p^r-1\mid p^s-1$

holds exactly when $r\mid s$. Therefore

$n\mid m.$

The two implications together prove that

\qquad\Longleftrightarrow\qquad n\mid m.$$## Verification For part (a), irreducibility of $f$ implies $\gcd(f,g)=1$ for every nonzero residue class $g$, and Bézout's identity yields an inverse. For part (b), the polynomial $x^m-1$ cannot have more roots than its degree. Since all $p^n-1$ nonzero elements are roots, $m\ge p^n-1$. Lagrange's theorem gives the opposite inequality. For part (c), when $n\mid m$, every element of the field satisfies $a^{p^m}=a$, so $x^{p^m}-x$ vanishes modulo $f$. Conversely, divisibility implies $p^n-1\mid p^m-1$, which is equivalent to $n\mid m$. Therefore all three assertions are established. This completes the proof. ∎