Reducibility of $x^2+1$ in $\mathbb{Z}_n[x]$

Question

I want to prove or disprove the statement:

$x^2+1$ is reducible in $\mathbb{Z}_n[x]$ $\iff$ there exists $a$ such that $a^2=-1$ in $\mathbb{Z}_n$.

How can I prove or disprove the proposition?

Answer 1

Counterexample: Take $n=3\cdot 7=21$. We have $$x^2+1=\left(7x^2+1\right)\left(15x^2+1\right)$$ in $(\mathbb{Z}/21\mathbb{Z})[x]$, but neither $7x^2+1$ nor $15x^2+1$ is a unit of this polynomial ring. Note that $a^2+1=0$ has no solution $a\in\mathbb{Z}/21\mathbb{Z}$ as such a solution would imply that $a^2+1=0$ holds in $\mathbb{Z}/3\mathbb{Z}$ as well as in $\mathbb{Z}/7\mathbb{Z}$, which is absurd.

However, maybe the statement "$x^2+1$ is reducible over $\mathbb{Z}/n\mathbb{Z}$ if and only if $a^2+1=0$ has a solution $a\in\mathbb{Z}/n\mathbb{Z}$" is true if we add the assumption (which should be a necessary and sufficient condition for the quoted statement to hold) that $n$ is a prime power. I will post a proof if I can show that my claim is true.

---

Generalization: Per request by lhf, I shall prove that $x^2+1$ is reducible over $\mathbb{Z}/n\mathbb{Z}$ if $n=p_1^{k_1}p_2^{k_2}\ldots p_r^{k_r}$, where the integer $r$ is at least $2$, the $p_i$'s are pairwise distinct prime natural numbers, and the $k_i$'s are positive integers. In fact, you can similarly show that every non-unit polynomial $p(x)$ in $(\mathbb{Z}/n\mathbb{Z})[x]$ which is not a unit element in $\left(\mathbb{Z}/p_i^{k_i}\right)[x]$ for at least two values of $i\in\{1,2,\ldots,r\}$ is reducible. For example, if $n=6$, then $$x+2=(3x+4)(4x+5)$$ in $(\mathbb{Z}/6\mathbb{Z})[x]$. Even more generally, let $S$ be a set of variables (it may be empty, finite, or infinite). We can define the polynomial rings $(\mathbb{Z}/n\mathbb{Z})[S]$ with variables in $S$ (where $(\mathbb{Z}/n\mathbb{Z})[\emptyset]$ is the ring $\mathbb{Z}/n\mathbb{Z}$ itself). Then, every non-unit polynomial in $( \mathbb{Z}/n\mathbb{Z})[S]$ which is not a unit element in $\left(\mathbb{Z}/p_i^{k_i}\right)[S]$ for at least two values of $i\in\{1,2,\ldots,r\}$ is reducible. For instance, $$x^2+2y+3=\left(5x^2+10y+11\right)\left(16x^2+12y+13\right)$$ in $(\mathbb{Z}/20\mathbb{Z})[x,y]$.

Consider $\mathbf{v}=\left(v_1,v_2,\ldots,v_r\right)\in\{0,1\}^r$. Define $a_\mathbf{v}$ and $b_\mathbf{v}$ to be the (unique) elements of $\mathbb{Z}/n\mathbb{Z}$ satisfying $a_\mathbf{v}\equiv v_i\pmod{p_i^{k_i}}$ and $b_\mathbf{v}\equiv 1-v_i\pmod{p_i^{k_i}}$ for all $i=1,2,\ldots,r$. Define $$f_\mathbf{v}(x):=a_\mathbf{v}\,x^2+1\text{ and }g_\mathbf{v}(x):=b_\mathbf{v}\,x^2+1\,.$$ Then, $x^2+1=f_\mathbf{v}(x)\,g_\mathbf{v}(x)$ over $\mathbb{Z}/n\mathbb{Z}$. Hence, there are at least $2^{r-1}-1\geq 1$ essentially different nontrivial factorizations of $x^2+1$ over $\mathbb{Z}/n\mathbb{Z}$.

Proof of Reducibility over $(\mathbb{Z}/n\mathbb{Z})[S]$: For constant polynomials, the claim is easy to verify (also, see the remark below). Let $p(S)\in(\mathbb{Z}/n\mathbb{Z})[S]$ be a non-constant polynomial satisfying the condition. Write $M(S)$ for the set of all monomials in variables in $S$ (note that $1\in M(S)$ always, even for $S=\emptyset$). Then, $p(S)=\displaystyle\sum_{m\in M(S)}\,t_m\,m$ for some $t_m\in\mathbb{Z}/n\mathbb{Z}$ with $m\in M(S)$ (note that all but finitely many $t_m$'s are zero). Let $\text{supp}\big(p(S)\big)$ denote the support of $p(S)$, i.e., the subset $T\supseteq \{1\}$ of $M(S)$ such that, for $m\in M(S)\setminus\{1\}$, $t_m\neq 0$ iff $m\in T$. Observe that $\{1\}\subsetneq \text{supp}\big(p(S)\big)$. Then, consider $$\mathbf{V}:=\left(\textbf{v}^i\right)_{i=1,2,\ldots,r}\in\left\{\textbf{a},\textbf{b}\right\}^r\,.$$ where $\textbf{a}=\left(a_m\right)_{m\in\text{supp}\big(p(S)\big)}$ satisfies $a_1=1$ and $a_m=0$ for all other $m$'s, whereas $\textbf{b}=\left(b_m\right)_{m\in\text{supp}\big(p(S)\big)}$ has $b_m=t_m$ for all $m$. Take $f_\textbf{V}(S),g_\textbf{V}(S)\in(\mathbb{Z}/n\mathbb{Z})[S]$ to be the polynomials $$f_\textbf{V}(S)=\displaystyle\sum_{m\in\text{supp}\big(p(S)\big)}\,\phi_m\,m\text{ and }g_\textbf{V}(S)=\displaystyle\sum_{m\in\text{supp}\big(p(S)\big)}\,\gamma_m\,m$$ where the $\phi_m$'s and the $\gamma_m$'s are the unique elements of $\mathbb{Z}/n\mathbb{Z}$ such that $\phi_1\equiv v^i_1\pmod{p_i^{k_i}}$, $\gamma_1\equiv 1+t_1-v^i_1\pmod{p_i^{k_i}}$, $\phi_m\equiv v^i_m\pmod{p_i^{k_i}}$ and $\gamma_m\equiv t_m-v^i_m\pmod{p_i^{k_i}}$, for all $i=1,2,\ldots,r$ and $m\in \text{supp}\big(p(S)\big)\setminus\{1\}$. Here, $\textbf{v}^i=\left(v_m^i\right)_{m\in\text{supp}\big(p(S)\big)}$ for each $i=1,2,\ldots,r$. It follows that $p(S)=f_\textbf{V}(S)\,g_\textbf{V}(S)$, and so $p(S)$ has at least $2^{\rho-1}-1\geq 1$ essentially distinct nontrivial factorizations in $(\mathbb{Z}/n\mathbb{Z})[S]$, where $\rho$ is the number of $i\in\{1,2,\ldots,r\}$ such that $p(S)$ is not a unit element in $\left(\mathbb{Z}/p_i^{k_i}\mathbb{Z}\right)[S]$.

Remark: All irreducible constant polynomials are indeed known. For example, $3$ is an irreducible element of $\mathbb{Z}/225\mathbb{Z}$. In fact, we have the following statement for all positive integers $r$ ($r=1$ included): $u\,p_1^{\nu_1}p_2^{\nu_2}\cdots p_r^{\nu_r}$, where $u$ is a unit element of $\mathbb{Z}/n\mathbb{Z}$ and $\nu_1,\nu_2,\ldots,\nu_r\in\mathbb{N}_0$, is an irreducible element of $(\mathbb{Z}/n\mathbb{Z})[S]$ if and only if there exists exactly one $i\in\{1,2,\ldots,r\}$ such that $\nu_i\neq 0$ and this $i$ must satisfy $\nu_i=1<k_i$. (As you can see, $7$ is reducible in $\mathbb{Z}/189\mathbb{Z}$ because $7=14\cdot 14$ in $\mathbb{Z}/189\mathbb{Z}$ and $14$ is not a unit element.)