# In Mod p Irreducibility Test for Z[t] Need p be Prime?

In descriptions of the mod $$p$$ irreducibility test it is always stated $$p$$ is prime. However is that restriction needed, since for any positive integer $$m$$ we have :

If $$m \nmid \mathrm{LC}(f)$$ and $$f \in \mathbb{Z}[t]$$ reducible then $$\psi(f) \in \mathbb{Z}_m[u]$$ is reducible,

where $$\psi$$ is the epimorphism $$: \mathbb{Z}[t] \rightarrow \mathbb{Z}_m[u]$$ defined by : $$\psi(a_n t^n + \ldots + a_0) = C_{a_n} u^n + \ldots + C_{a_0},$$

$$\mathrm{LC}(f)$$ is the leading coefficient of $$f$$, and $$C_x$$ is the congruence class mod $$m$$ of $$x \in \mathbb{Z}$$.

(Taking the definition of 'reducible' for a polynomial in $$R[X]$$ to mean 'is a product of two lesser degree polynomials in $$R[X]$$', for a general commutative unitary ring $$R$$).

Proof

Firstly note the definition of $$\psi$$ is consistent since any two expressions of $$f \in \mathbb{Z}[t]$$ in the form $$a_n t^n + \ldots + a_0$$ can only differ by leading zeros, and we can readily show $$\psi$$ is homomorphic using the properties $$C_{x + y} = C_x + C_y$$ and $$C_{xy} = C_x \cdot C_y$$ of congruence classes.

$$\psi$$ satisfies $$\partial\,\psi(f) \leq \partial f\; \forall f$$, with $$\psi$$ preserving degree if $$f = 0$$ or $$m \nmid \mathrm{LC}(f)$$, and reducing degree otherwise.

Then taking $$f \in \mathbb{Z}[t]$$ reducible, we have $$f = gh$$, where $$g \neq 0$$, $$h \neq 0$$, $$\partial g < \partial f$$, and $$\partial h < \partial f$$. Then

$$\psi(f) = \psi(g) \cdot \psi(h)$$

with : $$\begin{eqnarray*} \partial\,\psi(f) & = & \partial f \mbox{, since } m \nmid \mathrm{LC}(f) \\ \partial\,\psi(g) & \leq & \partial g < \partial f \\ \partial\,\psi(h) & \leq & \partial h < \partial f \end{eqnarray*}$$

which proves $$\psi(f) \in \mathbb{Z}_m[u]$$ is reducible.

Alternatively we could see that as $$\mathbb{Z}$$ is an integral domain : $$\begin{eqnarray*} & \mathrm{LC}(f) = \mathrm{LC}(g) \cdot \mathrm{LC}(h) \\ \Rightarrow & m \nmid \mathrm{LC}(g) \mbox{ and } m \nmid \mathrm{LC}(h) \\ \Rightarrow & \mbox{ we have } \partial\,\psi(f) = \partial f,\ \partial\,\psi(g) = \partial g,\ \partial\,\psi(h) = \partial h \end{eqnarray*}$$

ie. $$\psi$$ now preserves the degree of all three.

QED

Thus if such $$m \in \mathbb{N}$$ can be found with $$m \nmid \mathrm{LC}(f)$$ and $$\psi(f) \in \mathbb{Z}_m[u]$$ irreducible then $$f \in \mathbb{Z}[t]$$ is irreducible - and thus by Gauss's Lemma irreducible when considered as a polynomial in $$\mathbb{Q}[t]$$. So the test appears to work for composite $$p$$ also. If $$f$$ was monic any $$p > 1$$ could be tried. Is there any reason why it is usually stated for primes $$p$$ only ? With $$p$$ a prime, $$\mathbb{Z}_p$$ is a field, but with $$p$$ composite, $$\mathbb{Z}_p$$ is a commutative unitary ring but not an integral domain - but the argument applies just as well.

• the reason is that $A[X]$ has a nasty behavior when $A$ is not an integral domain. In general, $\deg(fg)\neq \deg(f)+\deg(g)$, $X$ may even be reducible, polynomials can have more roots than their degrees...So testing irreducibility in $\mathbb{Z}_n[X]$ for $n$ composite is even harder than in $\mathbb{Z}_p[X]$ (which is hard enough). Nov 5, 2021 at 16:09
• The definition of "irreducible element" is for element in an integral domains, and for $n$ not prime $\mathbb Z_n$ is not an integral domain. Nov 5, 2021 at 17:23