If $f(x)$ is a polynomial in $\mathbb{Z}$ and $f(a)\equiv k\pmod{n}$, prove that, for all integer $m$, $f(a+mn)\equiv k\pmod{n}$

Question

I'm trying to solve this excercise:

If $f(x)$ is a polynomial in $\mathbb{Z}$ and $f(a)\equiv k\pmod{n}$ . Prove that for all integer m

$f(a+mn)\equiv k\pmod{n}$.

I know that if $f(a)\equiv k\pmod{n}$ then there exist some $p\in\mathbb{Z}$ such that $f(a)-k=np$

But after this I don't know what to do. Any suggestion? Thanks!

Edit: I only can use basic properties of congruence.

Answer 1

Let $f(x)=c_0+c_1x+c_2x^2+\cdots+c_dx^d$.

Note that from binomial expansion $(a+mn)^k\equiv a^k\bmod n.$

Therefore $f(a+mn)=a_0+c_1(a+mn)+c_2(a+mn)^2+\cdots+c_d(a+mn)^d$

$\equiv a_0+c_1a+c_2a^2+\cdots+c_da^d=f(a)\bmod n$.

Answer 2

Reduction modulo $n$ is a ring homomorphism (i.e., preserves addition and multiplication). As $f(x)$ is computed from $x$ by a sequence of ring operations in $\Bbb Z$, it follows that $x\equiv y\pmod n$ implies $f(x)\equiv f(y)\pmod n$.

Answer 3

$a\equiv a + mn \pmod n$ to

$a^j \equiv (a+mn)^j\pmod n$ for all natural $j$

And $ca^j \equiv c(a+mn)^j \pmod n$ for all integers $c$ and

And for any polynomial with integer coefficients $f(x) =c_wx^w + .... + c_1x + c_0$ then $f(a)=\sum_{j=0}^w c_ja^j \equiv \sum_{j=0}^2 c_jx^j \equiv f(a+mn)\pmod n$.

So if $f(a) \equiv k\mod n$ then $f(a+mn) \equiv k \pmod n$>