Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$? 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?
 A: 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.    
