Tuesday, 1 October 2013

elementary number theory - Regarding the proof that if $a equiv b pmod{m} $ then $f(a) equiv f(b)pmod {m}$



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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...