Call a function $f : \mathbb Z \to \mathbb Z$ consistent if for every prime $p$ and integer $a, b$, when $a \equiv b \pmod p$ then $f(a) \equiv f(b) \pmod p$. The set $C$ of consistent functions is closed under addition, subtraction, composition, translation, and finite difference, and contains all univariate polynomials. Does $C$ contain only univariate polynomials, i.e. $C = \mathbb Z[x]$?
My intuition is that this must be the case. Since $f$ is well-defined $\mod p$ for every prime $p$, then I feel that $f$ must be defined based only on ring operations generically, so that the same definition of $f$ (with ring operations) works for any ring $\mathbb Z / p\mathbb Z$. Since the ring operations include only
- using 0, 1, and the variable $x$,
that would mean that $f$ must be a polynomial in $x$ with integer coefficients. Is this indeed the case?