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$).


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.


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.

  • 1
    $\begingroup$ 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). $\endgroup$
    – GreginGre
    Nov 5, 2021 at 16:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Desperado
    Nov 5, 2021 at 17:23


You must log in to answer this question.

Browse other questions tagged .