Let
\[P(x)\]
be a polynomial with integer coefficients. If \[a \equiv b \; (mod \; n)\]
then \[P(a) \equiv P(b) \; (mod \; n)\]
. In particular \[a\]
is a solution of \[P(x) \equiv 0 \; (mod \; n)\]
if and only if \[b\]
is also a solution.Proof
Let
\[P(x)=c_mx^m+c_{m-1}x^{m-1}+...+c_1x+c_0\]
.\[a^r \equiv b^r \; (mod \; n), \; ca^r \equiv cb^r \; (mod \; n), \rightarrow P(a) \equiv P(b) \; (mod \; n)\]
In particular,
\[P(a) \equiv 0 \; (mod \; n)\]
only if \[P(b) \equiv 0 \; (mod \; n)\]
and vice versa.