# If $f(x)$ is a polynomial and $f(n)$ is an integer for all $n\in \mathbb{Z}$, then $f(x)$ must have integer coefficients.

If $f(x)$ is a polynomial and $f(n)$ is an integer for all $n\in \mathbb{Z}$, then $f(x)$ must have integer coefficients.

I need to disprove the statement via a counter-example. But I can't seem to think of one. Could $3x^2+2x^{-1}+1$ be a possible example?

• How about $f(x)=x^2+\frac12x+1$ and $f(2)=6\in\Bbb{Z}$? – TheSimpliFire Sep 5 '18 at 18:23
• Need more details. Where must the coefficients of $f$ come from? Real numbers? And for all $n$, or only one $n$? – Randall Sep 5 '18 at 18:24
• What about $f(x) = \frac{x}{2} + \pi x^2 + i \cdot x^3$? It has $f(0)=0$, and $0$ is an integer. – lisyarus Sep 5 '18 at 18:24
• The example in the post is not a polynomial. – A. Pongrácz Sep 5 '18 at 18:40

Another family of simpe counter-examples: By Fermat's little theorem, $x^p\equiv x\pmod p$ for all $x\in\Bbb Z$ if $p$ is prime. Therefore $$\frac1px^p-\frac1px$$ maps integers to integers.

Are you after a polynomial $p(x)$ such that not all of its coefficients are integer but such that nevertheless you have $p(n)\in\mathbb Z$ for each integer $n$? You can take $p(x)=\frac12x^2+\frac12x$, for instance.

It is well known that the real polynomials with the given property are exactly the integer linear combinations of polynomials of the form $\binom{x}{n}$ (that is a binomial coefficient). José Carlos Santos' answer is a very good example which is almost exactly the simplest nontrivial one with non-integer coefficients, as $\frac{1}{2}x^2+\frac{1}{2}x = \binom{x}{2}+x$.

Try to prove the above by induction on the degree, or directly, it is not so hard. Then you have many counterexamples.

If you want something more than a quadratic try $$\frac 16(x^3-x)$$

• I am amazed by this but feel as though I shouldn't be. What's the argument for seeing this? – Randall Sep 5 '18 at 18:46
• Never mind, just got it. – Randall Sep 5 '18 at 18:51
• @Randall There are various ways of seeing it - I thought of $\binom xn$ and wanted you to think about this, and also (essentially the same thing) that $n!$ divides the product of $n$ consecutive integers. I just made $x$ the middle of the three. I find it is sometimes computationally convenient to make the product of an odd number of consecutive integers symmetric if you can choose. – Mark Bennet Sep 5 '18 at 19:47