Prove Proposition (3.9).
Proposition (3.9) is
Let $P (x) = c_0 + c_1x + c_2x^2 + ⋯ + c_{m−1}x^{m−1} + c_mx^m$ be an $m$th degree polynomial, that is $c_m ≢ 0 \pmod n$, where the coefficients $c_k$’s are integers.
If $a ≡ b \pmod n$ then $P (a) ≡ P (b) \pmod n$.
We start with $P(a)$
$$ P (a) = c_0 + c_1a + c_2a^2 + ⋯ + c_{m−1}a^{m−1} + c_ma^m $$
Since $a \equiv b \pmod n$
- by Proposition (3.8) we have $a^k \equiv b^k \pmod n$.
- by Proposition (3.6) $c_ja^k \equiv cjb^k \pmod n$.
And so
$$ \begin{align} P (a) & \equiv c_0 + c_1b + c_2b^2 + ⋯ + c_{m−1}b^{m−1} + c_mb^m \pmod n \\ \\ & \equiv P(b) \pmod n \end{align}$$
Which proves Proposition (3.9).