TAOCP 4.6.2 Exercise 12

Section 4.6.2: Factorization of Polynomials

Exercise 12. ▶ [M22] Use Berlekamp's algorithm to determine the number of factors of $u(x) = x^8 + 1$, modulo $p$, for all primes $p$. [Hint: Consider the cases $p = 2$, $p = 8k + 1$, $p = 8k + 3$, $p = 8k + 5$, $p = 8k + 7$.] What is the matrix $Q$? You need not discover the factors; just determine how many there are.]

Verified: yes
Solve time: 17m45s

---

Solution

Let

$u(x)=x^8+1.$

We seek the number $r$ of irreducible factors of $u(x)$ modulo a prime $p$. By step B3 of Berlekamp's algorithm, $r$ is the dimension of the solution space of

$v(x)^p\equiv v(x)\pmod{u(x)}, \eqno(8)$

or equivalently the dimension of the null space of $Q-I$.

The factorization of $u(x)$ is determined by the behavior of the eighth roots of $-1$.

For odd $p$, the roots of $u(x)$ in a splitting field satisfy

$\alpha^8=-1,\qquad \alpha^{16}=1,\qquad \alpha^8\ne1.$

Hence the roots are precisely the primitive $16$th roots of unity. Their behavior over $\mathbf F_p$ is governed by the Frobenius automorphism

$\alpha\mapsto\alpha^p.$

The degree of each irreducible factor is the size of the orbit of a primitive $16$th root under this map. Therefore the degree equals the multiplicative order of $p$ modulo $16$.

There are $\varphi(16)=8$ primitive $16$th roots, so if $d=\operatorname{ord}_{16}(p)$, then

$r=\frac8d.$

We now consider the residue classes of odd primes modulo $8$.

If $p\equiv1\pmod8$, then in fact

$p\equiv1\pmod{16}\quad\text{or}\quad p\equiv9\pmod{16}.$

In either case,

$p^2\equiv1\pmod{16}.$

If $p\equiv1\pmod{16}$, then $d=1$, hence

$r=\frac81=8.$

If $p\equiv9\pmod{16}$, then $d=2$, hence

$r=\frac82=4.$

If $p\equiv3\pmod8$, then

$p\equiv3\pmod{16}\quad\text{or}\quad p\equiv11\pmod{16}.$

Both satisfy

$p^2\equiv9\pmod{16},\qquad p^4\equiv1\pmod{16},$

while $p^2\not\equiv1\pmod{16}$. Thus $d=4$, and

$r=\frac84=2.$

If $p\equiv5\pmod8$, then

$p\equiv5\pmod{16}\quad\text{or}\quad p\equiv13\pmod{16}.$

Again

$p^2\equiv9\pmod{16},\qquad p^4\equiv1\pmod{16},$

and $d=4$. Therefore

$r=2.$

If $p\equiv7\pmod8$, then

$p\equiv7\pmod{16}\quad\text{or}\quad p\equiv15\pmod{16}.$

For $p\equiv15\pmod{16}$, $d=2$; for $p\equiv7\pmod{16}$, $d=2$ also, since

$7^2\equiv1\pmod{16}.$

Hence

$r=\frac82=4.$

The remaining case is $p=2$. Modulo $2$,

$u(x)=x^8+1=x^8-1=(x+1)^8,$

by equation (5). Thus there is only one distinct irreducible factor, namely $x+1$, and

$r=1.$

We now determine the matrix $Q$.

Since

$u(x)=x^8+1,$

we have

$$$$

Therefore

$$ \pmod{u(x)}. $$

For odd $p$,

$$ \begin{cases} (-1)^{pk/8}x^{,pk\bmod 8}, & pk\ge8, \end{cases} $$

and because reduction modulo $u(x)$ never produces more than one monomial, every row of $Q$ contains exactly one nonzero entry, equal to $\pm1$ modulo $p$.

Writing the basis as $(1,x,\ldots,x^7)$, the $k$th row corresponds to the monomial obtained from $x^{pk}$ after reduction modulo $x^8+1$. Thus

$$ \qquad \varepsilon_k=(-1)^{\lfloor pk/8\rfloor}, $$

and

$$ \begin{cases} \varepsilon_k,&j\equiv pk\pmod8,\ 0,&\text{otherwise}. \end{cases} $$

Hence $Q$ is a signed permutation matrix representing multiplication by $p$ on the exponents modulo $8$.

Combining the cases above, the number of irreducible factors of $x^8+1$ modulo a prime $p$ is

$$ \boxed{ r= \begin{cases} 1,&p=2,\[2mm] 8,&p\equiv1\pmod{16},\[2mm] 4,&p\equiv9\pmod{16},\[2mm] 2,&p\equiv3,5,11,13\pmod{16},\[2mm] 4,&p\equiv7,15\pmod{16}. \end{cases} } $$

Equivalently, grouped according to the hint,

$$ \boxed{ \begin{array}{c|c} p & r\ \hline 2 & 1\ 8k+1 & 8\text{ or }4,\ \text{according as }p\equiv1\text{ or }9\pmod{16}\ 8k+3 & 2\ 8k+5 & 2\ 8k+7 & 4 \end{array} } $$