When does a polynomial take all possible residues modulo any integer? (This question is inspired by a question about remainders of binomial coefficients I asked recently.)
Consider the polynomial maps $f:\ \mathbb{Z} \to \mathbb{Z}$. These include the polynomials with integer coefficients, but also functions like $f(x) = \frac{x(x-1)}{2} = \binom{x}{2}$. One can show that any such polynomial map $\mathbb{Z} \to \mathbb{Z}$ is a $\mathbb{Z}$-linear combination of the polynomials $\binom{x}{d}$ for $d \in \mathbb{N}$. I am interested in polynomial maps which take on all residues modulo all integers. More precisely, a polynomial $f$ is interesting for me if for any integer $m \geq 2$ and for any integer $0 \leq r < m$ there exists an integer $n$ with $f(n) \equiv r \pmod{m}$. One such polynomial is $f(x) = x$.
As explained in the mentioned other questions, polynomials $f(x) = x^d$ don't have the aforementioned property (for $d > 1$). I had a (naive) hope that the polynomials ${x \choose d}$ would do the trick, but they don't work either.
After some more thought, I discovered that degree $2$ polynomials can never work. This is because for $f(x) = ax^2 +bx +c$ the condition $f(n) \equiv r \pmod{p}$ can be rewritten as $$\left(n+\frac{b}{2a}\right)^2 \equiv \frac{1}{a}\left(r-c+\frac{b^2}{4a}\right) \pmod{p}$$ (assuming numerators and denumerators of $a,b,c$ are coprime to $p$). Hence, $f(n)$ does not have the residue $r$ if $p$ is large enough and $\frac{1}{a}\left(r-c+\frac{b^2}{4a}\right)$ is not a quadratic residue modulo $p$.
This leaves me doubtful about polynomials of higher degrees. I can't think of a general argument or an example of an interesting polynomial, though.
Question: Does there exist a polynomial map $f:\ \mathbb{Z} \to \mathbb{Z}$, different than $f(x) = x$, with the aforementioned property that for any integer $m \geq 2$ and for any integer $0 \leq r < m$ there exists an integer $n$ with $f(n) \equiv r \pmod{m}$. 
 A: We want to prove that $f(x)=x+a$ are the only posibilities.
Consider the polynomial $g(x)=f(x+1)-f(x)$. By looking at primes $p$, large enough, so that all denominators in the coefficients of $f$ are prime to $p$, we can assume $f$ has integer coefficients from now on. We want the congruences $f(x)=r\ (\text{ mod }p)$ to have solutions for all $r=0,1,\ldots,p-1$. Then $f(0),f(1),\ldots,f(p-1)$ must give all remainders $0,1,\ldots,p-1$. In particular they all must be different. Therefore $g(0),g(1),\ldots,g(p-1)$ are not zero mod $p$. Otherwise we don't get all the remainders out of $f$.
Lemma: If $g$ is non-constant then we can make $g(n)$ divisible by arbitrary large primes.
Proof: I wrote the proof of this lemma in this answer to another problem. 
Take $g(M)$ for $M$ very large such that $g(M)$ is divisible by a very large prime $p$ with the conditions above (such that this prime is prime with all denominators in the coefficients of $f$). Then $f(x)=r$ will not always be solvable mod this prime $p$.
Therefore $g$ is constant. Hence $f$ is linear. From this we get that the leading coefficient of $f$ must be $1$ and we get the solution $f(x)=x+a$, which works.
