I'm trying to follow proof of the following theorem in my book.
Theorem 2.2. Let $f$ denote a polynomial with integral coefficients. If $a \equiv b \pmod{m} $ then $f(a) \equiv f(b)\pmod {m}$.
I understand the proof fine, except for the bit I've coloured below:
Proof: We can suppose $f(x) = c_nx^n + c_{n-1}x^{n-1} + ... +c_{0}$ where the $c_i$
are integers. Since $a \equiv b (\pmod m)$ we can apply Theorem 2.1, part 4,
repeatedly to find $a^2 \equiv b^2, a^3 \equiv b^3, \cdots, a^n \equiv
b^n \pmod m$, and then
$\color{blue}{c_ja^j \equiv c_jb^j\pmod{m}}$ and finally $c_nba^n+c_{n-1}a^{n-1}+\cdots+c_0 \equiv c_nb^n+c_{n-1}b^{n-1}+\cdots+c_0$ by Theorem 2.1 part 3.
I don't understand what gives us that ${c_ja^j \equiv c_jb^j\pmod{m}}$? In fact, I'd expect that ${c_ja^j=c_jb^j\pmod{c_jm}}$ for any $c_j > 0$.
2.1 part 3 If $a \equiv b \pmod{m} $ and $c \equiv d \pmod{m}$ then $a+c \equiv b+d \pmod{m}$
2.1 part 4 If $a \equiv b \pmod{m} $ and $c \equiv d \pmod{m}$ then $ac \equiv bd \pmod{m}$.
Answer
$c_j \equiv c_j \pmod m$ and $a^j \equiv b^j \pmod m$ (from Theorem 2.1 part 4). Using Theorem 2.1 part 4 on these two gives the required result.
No comments:
Post a Comment