# Property of a polynomial $f\in\mathbb{Q}[X]$ such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$?

We can always view $\binom{x}{k}$ as a polynomial in $x$ of degree $k$. With this in mind, why is it so that a polynomial $f\in\mathbb{Q}[x]$ is such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$ iff the coefficients of $f$ in terms of the basis $\{\binom{x}{k}\mid k\in\mathbb{N}\}$ are also integers?

I thought it might be useful to note that $0,1,\dots,k-1$ are roots of $\binom{x}{k}$, but I still don't see why such a property would be true. Thanks for an explanation.

-

Since the binomial coefficients for integer $x$ are integers, clearly $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$ if the coefficients are integers.

For the other direction, assume that not all of the coefficients are integers. Then there is a least coefficient, say the $m$-th, that isn't an integer. Substituting $m$ for $x$ yields an integer coefficient times an integer for $k\lt m$, a non-integer coefficient times $1$ for $k=m$, and $0$ for $k\gt m$. Thus the value at $m$ is not an integer.

-
Thanks, joriki! – megyn Dec 15 '11 at 1:39

Another reason is that the higher-order differences of the values of a polynomial function are eventually zero. Going backwards, one finds an expression for the polynomial in terms of Newton polynomials with coefficients the first element in each row of differences; see http://en.wikipedia.org/wiki/Newton_series#Newton.27s_series.

-

Another way to look at it(that is catching the essence of joriky argument that is,working in a triangular matrix): taken a basis of the polynomial in Q with degree less equal than n,coefficient in Z, consider the matrix $a_{i,j}=p_j(i)$ where j and i vary on $\{0,..,n\}$ ( $p_j$ is of course one of the element of the basis). Now the vector (f(0),..f(n)),is given by applying that matrix to the vector of coefficient of f,that in general lies in ${\mathbb{Q}}^{n+1}$, so to be able to deduce that the coefficients are in ${\mathbb{Z}}^{n+1}$ you need that the inverse of that matrix is still with coefficient in Z,this is equivalent to ask that the determinant of that matrix is 1 or -1. So this is the general criterion,in your case this is evidently true,since you have a triangular matrix with 1 on the diagonal so determinant is 1(and here is the tangency with joriky argument) Bye!

-