## Factor a given polynomial into irreducibles over different rings

Completely factor $p(x) = x^8 - 1$ and $q(x) = x^6 - 1$ over $\mathbb{Z}$, $\mathbb{Z}/(2)$, and $\mathbb{Z}/(3)$.

Note that over any ring with 1 we have $p(x) = (x^4+1)(x^2+1)(x+1)(x-1)$ and $q(x) = (x^2+x+1)(x^2-x+1)(x+1)(x-1)$.

Over $\mathbb{Z}$, $x^4+1$ is irreducible since $(x+1)^4 + 1 = x^4 + 4x^3 + 6x^2 + 4x + 2$ is Eisenstein at 2. Also, $x^2+1$ is irreducible since $(x+1)^2 + 1 = x^2 + 2x + x$ is Eisenstein at 2. Thus $p(x) = (x^4+1)(x^2+1)(x+1)(x-1)$ is completely factored into irreducibles.

Similarly, $x^2 + x + 1$ is irreducible since $(x+1)^2 + (x+1) + 1 = x^2 + 3x + 3$ is Eisenstein at 3, and $x^2 - x + 1$ is irreducible since $(x-1)^2 - (x-1) + 1 = x^2 - 3x + 3$ is Eisenstein at 3. Thus $q(x) = (x^2 + x + 1)(x^2 - x + 1)(x+1)(x-1)$ is completely factored into irreducibles.

In this previous exercise, we computed the irreducible monic polynomials of degree at most 3 over $\mathbb{Z}/(2)$ and $\mathbb{Z}/(3)$.

Over $\mathbb{Z}/(3)$, $r(x) = x^4 + 1$ has no linear factors since $r(0) = 1$ and $r(1) = f(2) = 2$. Suppose now that $r(x)$ has a quadratic factor; say $x^2 + ax + b$. Using the polynomial long division algorithm, we see that $r(x) = (x^2 + ax + b)(x^2 - ax + (a^2 - b)) + (2ab - a^3)x + (1 - a^2b + b^2)$. Thus $2ab - a = a(2b-1) = 0$ and $1 - a^2b + b^2 = 0$. If $a = 0$, then the second equation gives $b^2 = -1$, a contradiction. Thus $2b - 1 = 0$, so that $b = 2$. Now we have $a^2 = 1$, so that $a \in \{1,2\}$. Indeed, $x^4 + 1 = (x^2 + x + 2)(x^2 + 2x + 2)$, and these factors are irreducible.

Evidently, $p(x) = (x + 1)^8$ and $q(x) = (x^2 + x + 1)^2(x+1)^2$ are completely factored over $\mathbb{Z}/(2)$ and $p(x) = (x^2 + x + 2)(x^2 + 2x + x)(x^2 + 1)(x+1)(x+2)$ and $q(x) = (x+1)^3(x+2)^3$ are completely factored over $\mathbb{Z}/(3)$.