Are certain integer functions well-defined modulo different primes necessarily polynomials?

Solution 1:

Consider the function

$$ f(z) = z \sum_{m=1}^\infty \prod_{n=1}^m (z^2 - n^2) $$

This is well-defined on the integers, since all but finitely many terms are $0$ at any integer $z$. Moreover, for any positive integer $p$ (prime or not), $x \equiv y \mod p$ implies $f(x) \equiv f(y) \mod p$, because that is true for each of the summands $z \prod_{n=1}^m (z^2 - n^2)$. But $f(z) \ge z!$ for $z\ge 2$, so this is not a polynomial.

Solution 2:

There are uncountably many consistent functions, and so they certainly are not all polynomials with integer coefficients. Consider the process where you define a consistent function $f$ by defining the values $f(0),f(1),f(-1),f(2),f(-2),\dots$ one by one. At each step, when you are defining $f(n)$, you have a constraint on the value of $f(n)$ mod $p$ for each $p$ such that you have already defined $f(m)$ for some $m$ which is congruent to $n$ mod $p$ (note that there might be multiple such $m$ for any given $p$, but they all give the same constraint because we have constructed $f$ to be consistent up to this point). But this is a finite set of primes, and so by the Chinese Remainder Theorem these constraints mod $p$ are just equivalent to constraining the value of $f(n)$ mod the product of all these primes. In particular, there are infinitely many choices for what you can make $f(n)$ be.

So you can construct consistent functions in infinitely steps where at each step you have infinitely many choices, and this gives uncountably many choices.