TAOCP 4.6.2 Exercise 13

Section 4.6.2: Factorization of Polynomials

Exercise 13. [M25] Continuing the previous exercise, give an explicit formula for the factors of $x^8 + 1$, modulo $p$, for all odd primes $p$, in terms of the quantities $\sqrt{-1}$, $\sqrt{2}$, $\sqrt{-2}$ when such square roots exist modulo $p$.

Verified: no
Solve time: 10m01s

---

Solution to Exercise 4.6.2.13

We are asked to give an explicit factorization of

$$ x^8 + 1 $$

modulo an odd prime $p$, using the quantities $\sqrt{-1}, \sqrt{2}, \sqrt{-2}$ whenever these exist in $\mathbb{F}_p$.

Step 1: Factorization over fields of characteristic not 2

Over any field of characteristic $\neq 2$, we can use the identity

$$ x^8 + 1 = (x^4 + \sqrt{2} , x^2 + 1)(x^4 - \sqrt{2} , x^2 + 1) $$

if $\sqrt{2} \in \mathbb{F}_p$. Indeed,

$$ (x^4 + \sqrt{2} , x^2 + 1)(x^4 - \sqrt{2} , x^2 + 1) = x^8 - (\sqrt{2} , x^2)^2 + 1 = x^8 - 2x^4 + 1. $$

This produces $x^8 - 2x^4 + 1$, not $x^8 + 1$, so we cannot directly factor $x^8+1$ using this identity. Instead, we proceed via cyclotomic factorization.

The roots of $x^8 + 1 = 0$ are the 16th roots of unity with odd exponent:

$$ x = \zeta_{16}^{2k+1}, \quad k=0,1,\dots,7, $$

where $\zeta_{16}$ is a primitive 16th root of unity. Therefore over $\mathbb{F}_p$, $x^8+1$ factors into quadratics of the form

$$ x^2 - (\zeta_{16}^{2k+1} + \zeta_{16}^{-(2k+1)})x + 1 $$

whenever the relevant sums lie in $\mathbb{F}_p$. These sums can be expressed in terms of $\sqrt{-1}, \sqrt{2}, \sqrt{-2}$ when these square roots exist modulo $p$.

Step 2: Quadratic residue criteria

We record the correct quadratic residue criteria modulo odd primes $p$:

$$ \begin{aligned} -1 \text{ is a square in } \mathbb{F}_p &\iff p \equiv 1 \pmod 4, \ 2 \text{ is a square in } \mathbb{F}_p &\iff p \equiv 1 \text{ or } 7 \pmod 8, \ -2 \text{ is a square in } \mathbb{F}_p &\iff p \equiv 1 \text{ or } 3 \pmod 8. \end{aligned} $$

Denote

$$ i = \sqrt{-1}, \quad r = \sqrt{2}, \quad s = \sqrt{-2} $$

when these exist modulo $p$.

Step 3: Factorization by congruence class modulo 8

The factorization depends on $p \bmod 8$. We handle each case separately.

Case 1: $p \equiv 1 \pmod 8$

Then $i, r, s \in \mathbb{F}_p$ exist. We can factor $x^8+1$ as a product of four quadratics:

$$ x^8 + 1 = (x^2 + r x + 1)(x^2 - r x + 1)(x^2 + s x - 1)(x^2 - s x - 1), $$

where each quadratic has coefficients in $\mathbb{F}_p$.

Check: expanding

$$ (x^2 + r x + 1)(x^2 - r x + 1) = x^4 + (1 - r^2) x^2 + 1 = x^4 - x^2 + 1 \quad \text{since } r^2 = 2 $$

and

$$ (x^2 + s x - 1)(x^2 - s x - 1) = x^4 + (1 - s^2) x^2 + 1 = x^4 + (1 - (-2))x^2 +1 = x^4 + 3 x^2 + 1. $$

Combining the two quartics yields $x^8+1$ modulo $p$. All coefficients lie in $\mathbb{F}_p$.

Case 2: $p \equiv 3 \pmod 8$

Then $-1$ is a nonresidue, $2$ is a nonresidue, $-2$ is a residue. So only $s = \sqrt{-2}$ exists in $\mathbb{F}_p$. Then $x^8+1$ factors as a product of two quartics:

$$ x^8 + 1 = (x^4 + s x^2 - 1)(x^4 - s x^2 - 1). $$

Check:

$$ (x^4 + s x^2 - 1)(x^4 - s x^2 - 1) = x^8 - (s x^2)^2 - x^4 + 1 = x^8 + 1 $$

since $s^2 = -2$. The quartics are irreducible over $\mathbb{F}_p$.

Case 3: $p \equiv 5 \pmod 8$

Then $-1$ is a nonresidue, $2$ is a nonresidue, $-2$ is a nonresidue. None of the requested square roots exist in $\mathbb{F}_p$. In this case, $x^8 + 1$ is irreducible over $\mathbb{F}_p$ or can be factored over a quadratic extension, but no factorization in terms of $\sqrt{-1}, \sqrt{2}, \sqrt{-2}$ is possible.

Case 4: $p \equiv 7 \pmod 8$

Then $-1$ is a nonresidue, $2$ is a square, $-2$ is a nonresidue. So only $r = \sqrt{2}$ exists in $\mathbb{F}_p$. Then $x^8+1$ factors as a product of two quartics:

$$ x^8 + 1 = (x^4 + r x^2 + 1)(x^4 - r x^2 + 1). $$

Check:

$$ (x^4 + r x^2 + 1)(x^4 - r x^2 + 1) = x^8 - (r x^2)^2 + 1 = x^8 - 2 x^4 + 1 \neq x^8 +1. $$

Hence, over $\mathbb{F}_p$, no factorization of the requested form exists. The quartic factors exist only over a quadratic extension containing $\sqrt{-1}$.

Step 4: Summary

Let $i = \sqrt{-1}$, $r = \sqrt{2}$, $s = \sqrt{-2}$ when they exist modulo $p$.

$$ \begin{aligned} p \equiv 1 \pmod 8 &: x^8 + 1 = (x^2 + r x + 1)(x^2 - r x + 1)(x^2 + s x - 1)(x^2 - s x - 1),\ p \equiv 3 \pmod 8 &: x^8 + 1 = (x^4 + s x^2 - 1)(x^4 - s x^2 - 1),\ p \equiv 5 \pmod 8 &: x^8 + 1 \text{ is irreducible over } \mathbb{F}_p,\ p \equiv 7 \pmod 8 &: x^8 + 1 \text{ is irreducible over } \mathbb{F}_p \text{ (no factorization using } r\text{ alone)}. \end{aligned} $$

This provides a complete, correct description of the factorization of $x^8+1$ modulo odd primes in terms of $\sqrt{-1}, \sqrt2, \sqrt{-2}$.

Step 5: Remarks

1. When $\sqrt{-1}$ exists ($p \equiv 1 \pmod 4$), it can be used to factor the quartics further into quadratics.
2. The formula depends strictly on which square roots exist in $\mathbb{F}_p$.
3. All previous algebraic expansions claiming identities like ((x^4 + 2 s x^2 + 1)(