Solutions of Polynomial Congruences

Theorem

Let $P \left({x}\right)$ be an integral polynomial.

Let $a \equiv b \pmod n$.

Then $P \left({a}\right) \equiv P \left({b}\right) \pmod n$.

In particular, $a$ is a solution to the polynomial congruence $P \left({x}\right) \equiv 0 \pmod n$ iff $b$ is also.

Proof

Let $P \left({x}\right) = 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 $c_r a^r \equiv c_r b^r \pmod n$ for each $r \in \Z: r \ge 1$.

From Modulo Addition we then have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle P \left({a}\right)\)	\(=\)	\(\displaystyle c_m a^m + c_{m-1} a^{m-1} + \cdots + c_1 a + c_0\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle c_m b^m + c_{m-1} b^{m-1} + \cdots + c_1 b + c_0\)	\(\displaystyle \)	\(\displaystyle \pmod n\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\equiv\)	\(\displaystyle P \left({b}\right)\)	\(\displaystyle \)	\(\displaystyle \pmod n\)	\(\displaystyle \)

In particular, $P \left({a}\right) \equiv 0 \iff P \left({b}\right) \equiv 0 \pmod n$.

That is, $a$ is a solution to the polynomial congruence $P \left({x}\right) \equiv 0 \pmod n$ iff $b$ is also.

$\blacksquare$