If f(n) is congruent to r(mod m), is f(km + n) congruent to r(mod m)?

Question

I am currently working on a number theory book and I came across a question about the divisibility of two consecutive cubes. While solving it, I realized that my solution relied on the following to be true:

If $f(x)$ is some function with integer coefficients and if $f(n) \equiv r\pmod{m}$ for some integer n, then $f(km+n) \equiv r\pmod{m}$ where $k$ is any integer.

I do not know if this is true, but I have tried many examples and they seem to work. Here's one such example I just made up:

Let $f(x) = x^2 + x + 1$. Then $f(2) = 7 \equiv 3\pmod{4}$ and letting $k$ being defined as above,

let $k=1$:

$f(2+4)$ = $f(6) = 43 \equiv 3\pmod{7}$

let $k=2$:

$f(2+(2\times4))$ = $f(10) = 111 \equiv 3\pmod{7}$.

Is the statement above always true? Is it "obvious"? How can I think about this?

It seems that the statement is true, but not obvious--or at least not trivial to me.

Thank you!

Answer 1

Yes, if $\,f(x)\,$ is a polynomial with integer coefficients then

$${\rm mod}\ m\!:\,\ A\equiv a\,\Rightarrow\, f(A)\equiv f(a) $$

For a proof see the Polynomial Congruence Rule. Hint: since polynomials are compositions of sums and products, the proof follows by induction on degree, using Congruence Sum and Product rules: $$\,A\equiv a,\, B\equiv b\ \Rightarrow\ A+B\equiv a+b,\ AB\equiv ab$$

Answer 2

My simple proof,

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

We see that from binomial expansion $(km+n)^t\equiv a^t\bmod m.$

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

$f(km+n)\equiv \underbrace{a_0+c_1a+c_2a^2+ \cdots +c_da^d}_{\text{Terms without }km} = f(n) = r\bmod m$.