Question

Let \(f(x)\) be a polynomial in x with integral coefficients. Show, if \(a\equiv b (\mod m)\), then \(f(a)\equiv f(b)(\mod m)\)

Answer 1

One way to think of this is that you want to show if \(m\) divides \(a-b\), then \(m\) divides \(f(a)-f(b)\).

Answer 2

Another way is to show that if \(a\equiv b \pmod{m}\), then \(a^n\equiv b^n\pmod{m}\) for all natural numbers n. Then your result will follow.

Answer 3

The first way i mentioned is easier if you know a small fact about polynomials with integer coefficients.

Answer 4

Second is better if you like modular arithmetic.

Answer 5

what fact? I guess i don't know..

Answer 6

If \(f(x)\) is a polynomial with integer coefficients, and \(a\) and \(b\) are distinct integers, then \(a-b\) always divides \(f(a)-f(b)\).

Answer 7

I guess, i still haven't learned that fact in school.. But it makes the solution super easy..
Well, how do we proceed by second method?

Answer 8

You can reduce the powers of x modulo a in the polynomial, so the result will follow.

Answer 9

First you need to show that \(a\equiv b \pmod{m}\) implies that \(a^n \equiv b^n\pmod{m}\) for any natural number \(n\). This can be done by induction. Let \(f(x)=\sum_{k=0}^nc_kx^k\). Then \[f(a)=\sum_{k=0}^nc_ka^k\equiv \sum_{k=0}^nc_kb^k=f(b)\pmod{m}.\]You can swap the powers of a for powers of b since they are equivalent modulo m.

Answer 10

I haven't practiced modular arithmetic much.. I don't get it.. can you please explain a bit.
I know that if \(a\equiv b (\mod m)\), then \(a^m\equiv b^m (\mod m)\) But i don't get after it..

Answer 11

Just try it out with an example. Let \(f(x)=3x^2+2x+1.\) Let \(a=4\), \(b=9\), and \(m=5\). Then we know that since \(4\equiv 9\pmod{5}\), it follows that \(4^n\equiv 9^n\pmod{5}\) for all natural numbers \(n\).

Therefore:
\[f(4)=3(4)^2+2(4)+1.\]Since \(4\equiv 9\pmod{5}\) and \(4^2\equiv 9^2\pmod{5}\)(by the first arguement), we can swap them out:
\[f(4)=3(4)^2+2(4)+1\equiv 3(9)^2+2(9)+1=f(9)\pmod{5}.\]

Answer 12

Basically you don't touch the coefficients of the polynomial, you only swap the powers of a and b, since they are equivalent modulo \(m\).

Answer 13

Basically the integers modulo m form a ring under the classical definitions of multiplication and addition, so that is why we can 'swap' them out.

Answer 14

I guess, I get it now.. Thanks! :)