Solutions of Polynomial Congruences

Theorem

Let $\map P x$ be an integral polynomial.

Let $a \equiv b \pmod n$.

Then:

$\map P a \equiv \map P b \pmod n$

In particular, $a$ is a solution to the polynomial congruence $\map P x \equiv 0 \pmod n$ if and only if $b$ is also.

Let $\map P x = c_m x^m + c_{m - 1} x^{m - 1} + \cdots + c_1 x + c_0$.

Since $a \equiv b \pmod n$, from Congruence of Product and Congruence of Powers, we have:

$\forall r \in \Z_{>0}: c_r a^r \equiv c_r b^r \pmod n$

From Modulo Addition we then have:

$\ds \map P a$

$=$

$\ds c_m a^m + c_{m - 1} a^{m - 1} + \cdots + c_1 a + c_0$

$\ds $

$\equiv$

$\ds c_m b^m + c_{m - 1} b^{m - 1} + \cdots + c_1 b + c_0$

$\ds \pmod n$

$\ds $

$\equiv$

$\ds \map P b$

$\ds \pmod n$

In particular:

$\map P a \equiv 0 \iff \map P b \equiv 0 \pmod n$

That is, $a$ is a solution to the polynomial congruence $\map P x \equiv 0 \pmod n$ if and only if $b$ is also.

$\blacksquare$