= Polynomial congruence
{title2=$f(x)\equiv0\pmod m$}
A polynomial congruence asks for integer residue classes satisfying an equation such as
$$
f(x)\equiv0\pmod m,\qquad f\in\mathbb Z[x],\quad m\geq1.
$$
Integer coefficients ensure that replacing $x$ by a congruent integer changes $f(x)$ by a multiple of $m$. The problem is therefore an equation in the quotient ring $\mathbb Z/m\mathbb Z$, rather than infinitely many unrelated integer tests.
For $x^2\equiv1\pmod8$, the solutions are $1,3,5,7$ modulo eight. This quadratic has four roots because the quotient ring has zero divisors: $(x-1)(x+1)=0$ does not force either factor to vanish individually. Over a prime modulus, a nonzero degree-$d$ polynomial has at most $d$ roots because the quotient is a field. The nonzero-polynomial qualification matters if all coefficients vanish modulo the prime.
For coprime moduli, the <Chinese remainder theorem> combines solutions componentwise. Thus solving modulo prime powers and then recombining is a natural strategy; lifting between powers of one prime introduces additional conditions, as in <Hensel's lemma>.
Back to article page
