In the answer to this previous question , Noam D. Elkies proved that for any integer $x$, $x^3-x^2-2x+1$ can only have a divisors equal to $-1$, $0$, or $1$ modulo $7$. I would like to know what is known about this type of questions in general.
Most generally, is there an algorithm that, given a polynomial $P$ in variables $z_1,\dots,z_n$ with integer coefficients, and integers $m,a,b$, determines where there exist integers $z_1,\dots,z_n$ such that $P(z_1,\dots,z_n)=x \cdot y$ for $x \equiv a \, (\text{mod} \, m)$ and $y \equiv b \, (\text{mod} \, m)$? This is equivalent to Hilbert 10-th problem for the equations of the form $(mx+a)(my+b)=P(z_1,\dots,z_n)$.
In particular, is there an algorithm that, given a polynomial $P$ as above, and integers $m,a,b$, determines where there exist integers $z_1,\dots,z_n$ such that $P(z_1,\dots,z_n)$ has a divisor $x$ such that $x \equiv a \, (\text{mod} \, m)$ ?
As a special case, what if $P(z)$ is a polynomial in one variable?
An even more special case, what if $P(z)$ is (a) cubic, or (b) quartic?
