Factorization in the ring $\mathbb{Z}[x]/(x^2+1)\mathbb{Z}[x]\cong \mathbb{Z}[i]$ is well known. For instance, $5$ and $13$ (and any prime $\equiv 1\pmod{4}$) are no longer prime.
The factorization of $5$ lifts to $\mathbb{Z}[x]/((x^2+1)^2)\mathbb{Z}[x]$, but it isn't a simple consequence of Hensel's lemma. The trouble with using Hensel's lemma is that it requires a form of Bezout's identity, which does not generally hold over $\mathbb{Z}[x]$. Instead, for any two coprime polynomials $a,b\in \mathbb{Z}[x]$, all we know in $\mathbb{Z}[x]$ is that there exists some polynomials $c,d\in \mathbb{Z}[x]$ such that $ac+bd\in \mathbb{Z}-\{0\}$.
For example, $1+2x$ and $1-2x$ are relatively prime, but the "smallest" positive integer that is a linear combination is
$$
(1+2x)+(1-2x) = 2.
$$
Note that $5=(1+2x)(1-2x) + 4(1+x^2)$, and the coefficient on $(1+x^2)$ is divisible by $2$. This lucky coincidence is what allows us to lift the factorization of $5$.
The factorization of $13$ as $(2+3x)(2-3x)\pmod{(1+x^2)}$ also lifts (as pointed out in the comments below by Johan). Here, the smallest positive integer $\mathbb{Z}[x]$-linear combination of $2+3x$ and $2-3x$ is $4$, and that's not enough. But the smallest $\mathbb{Z}[x]$-linear combination of $2+3x$, $2-3x$, and $1+x^2$ is $1$, which is enough.
Question: Given a monic irreducible polynomial $q(x)\in \mathbb{Z}[x]$, of degree at least $2$, and an integer $n\geq 2$, is there some integer prime $p$ that factors in $\mathbb{Z}[x]/q(x)^n\mathbb{Z}[x]$?
This question arose thinking about this problem.
Best Answer
Assume that $\mathcal{O} = \mathbb{Z}[x]/(q(x))$ is the ring of integers of a number field $K$. One can search for a prime $p$ which is not inert in $\mathcal{O}$ and such that there is a principal prime ideal above $p$. I think such primes exist because the density of principal prime ideals is $1/h$, where $h$ is the class number of $\mathcal{O}$ (see this question), and because the prime ideals of $\mathcal{O}$ lying above an inert prime have density 0 (because their norm is $p^{[K:\mathbb{Q}]}$).
Write $p \mathcal{O} = \mathcal{P} \cdot I$ where $\mathcal{P} = (a)$ is a prime ideal, $I = (b) \neq \mathcal{O}$ is coprime to $\mathcal{P}$ and $p=ab$ in $\mathcal{O}$. Then you will have $p=a(x)b(x)+q(x)r(x)$ for some $a(x), b(x), r(x) \in \mathbb{Z}[x]$, and Hensel's lemma will work because $\langle a(x), b(x), q(x) \rangle = \mathbb{Z}[x]$. It will give a factorisation of $p$ in $\mathbb{Z}[x]/(q(x))^n$ for every $n \geq 2$.