Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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}$.

share|improve this question
We may be thinking of different definitions, but I can't see how $\,f(x)=\frac x{x-1}\;$ can be considered a polynomial map... –  DonAntonio Jul 29 '13 at 18:35
@DonAntonio: It was supposed to be $x(x-1)/2$. Corrected. Thanks for pointing this out! –  Feanor Jul 29 '13 at 18:36
@RGB: Are you sure? As far as I understand, for $f(x) = x^2$ what you say is not true. The law of quadratic reciprocity seems to imply that for appropriate choice of $p \pmod{ 4p_1p_2\dots p_k}$ I can ensure that all primes $p_1,p_2,\dots,p_k$ are quadratic residues modulo $p$. Hence, $f(x) \equiv r \pmod{p}$ has solutions for $r$ up to $p_{k+1}$, which can be made larger than $d$. –  Feanor Jul 29 '13 at 18:55

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.