Proof That Solutions of Polynomial Congruence are Well Defined

Theorem
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.

Add comment

Security code
Refresh