Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$?

Question

Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$ ?

I know polynomials do; are there others?

Answer 1

There are such functions which are not polynomials. We will construct an example of a function $g$ which grows faster than any polynomial, and such that for all integers $m \ge 1$, and all non-negative integers $x$ and $y$, if $x \equiv y \pmod{m}$, then $g(x)\equiv g(y)\pmod{m}$. It will follow immediately that if $f(x)=g(x^2)$, then for all integers $x$, $y$, if $x \equiv y \pmod{m}$ then $f(x) \equiv f(y)\pmod{m}$, and $f$ is not a polynomial.

Let $g(0)=1$. Suppose that we have defined $g(k)$ for all non-negative $k<n$. We show how to define $g(n)$. It is easy to find a polynomial $P_n(x)$, with integer coefficients, such that $P_n(k)=g(k)$ for all integers $k$ with $0 \le k <n$. Let $g(n)= P_n(n)+(A_n)(n!)$, where $A_n$ is chosen so that (say) $g(n)>2^n$ (this part is to make sure that $g$ grows faster than any polynomial).

Suppose that $g$ has the desired congruence property for all $x$, $y$ with $0 \le x, y <n$. We show it has the desired congruence property for $0 \le x, y \le n$. Let $0 \le x <n$. If $m$ is positive and $x \equiv n \pmod{m}$, then $m \le n$, so $g(n) \equiv P_n(n) \pmod{m}$. But $P_n(x)\equiv P_n(n)\pmod{m}$, since $P_n$ is a polynomial.