Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there an example of a rational polynomial $f(n)\in \mathbb{Q}[t]$ that has integer output for all integer inputs that are sufficiently large, but not for, say, inputs $n=1,2,3,\dots,n$?

share|cite|improve this question
up vote 2 down vote accepted

No. If $f$ has degree $d$, you can reconstruct $f(n-1)$ from $f(n), \ldots, f(n+d)$ by taking repeated differences and adding again.

share|cite|improve this answer
So a rational polynomial that has integer outputs for sufficiently high integer inputs must in fact have integer outputs for ALL integer inputs? – Helmut Oct 16 '12 at 13:33
Yes. For example a quadratic polynomial with $f(10)=a$, $f(11)=b$, $f(12)=c$ integers will have first differences $b-a, c-b$ and second difference $c-2b+a$; hence the first differences continue to the left with $b-a-(c-2b+a)=-2a+3b-c$, thus $f(9)=a-(-2a+3b-c)=3a-3b+c$. – Hagen von Eitzen Oct 16 '12 at 22:19

Any $P\in\mathbb Q[X]$ whose evaluations at all $n \in\Bbb N$ are in $\Bbb Z$ are integer linear combinations of the rational polynomials $\binom Xd$ with $d \in\Bbb N$: the coefficient of $\tbinom X0=1$ is the evaluation $P$ at $0$; subtracting off that (constant) term, the coefficient of $\tbinom X1=X$ is the evaluation at $1$ of the remainder; subtracting off that (linear) term, the coefficient of $\tbinom X2=\frac{X^2-X}2$ is the evaluation at $2$ of the remainder; and so forth. The remainder ultimately becomes $0$ when the coefficient of $\binom Xd$ is taken into account where $d=\deg P$, as we have subtracted off a polynomial $Q$ of degree $d$ whose evaluations in $0,1,\ldots,d$ coincide with those of $P$, which forces $P=Q$.

Now the rational polynomials $\tbinom Xd$ take integer values at all $n\in\Bbb Z$, and therefore so will $P$. If for some $P'\in\mathbb Q[X]$ the evaluations at all integers${}\geq n_0$ are in $\Bbb Z$, then consider $P=P'[X:=X+n_0]$ (substitute $X+n_0$ for $X$), now $P$ has integer evaluations at all $n \in\Bbb N$, and the above applies, so $P'$ has integer evaluations at all $n \in\Bbb Z$.

To make the link with answer by Hagen von Eitzen, this argument only needs the integrality at $\deg P+1$ successive values, which forces all evaluations to be integer.

share|cite|improve this answer


Suppose $f$ is a polynomial in $\mathbb{Q}[x]$ outputting integers for sufficiently large integer inputs. Then I claim $f$ can be written $$ \sum_{i = 0}^n a_i {x \choose i} $$ where $$ {x \choose i} = \frac{x(x-1)\ldots(x-i+1)}{i!} $$ and the $a_i$ are integers; note that this expression is $1$ when $i = 0$ (because the numerator is the empty product). This claim then proves your result, since clearly anything that can be written this way has your property.

The proof: Clearly we can write $f$ this way for some rational numbers $a_i$. We will recover the $a_i$ and then argue that they must be integers. If $g$ is a polynomial, set $$ \Delta g = g(x+1) - g(x). $$ We compute (just by writing it out) that $$ \Delta {x \choose i} = {x \choose i -1} $$ for $i > 0$ and clearly $\Delta {x \choose 0} = 0$.

Since $\Delta$ is linear, it follows that \begin{align*} a_0 =& f(0) & \\ a_1 =& (\Delta f)(0)\\ a_2 =& (\Delta^{(2)} f)(0)\\ \ldots \\ a_n =& (\Delta^{(n)}f)(0)\\ \end{align*}

With these formulas and induction on the degree of $f$, we have that all of the coefficients but $a_0$ must be integers (because the polynomials $\Delta^{(i)}(f)$ have smaller degree, they must evaluate to integers on all integers). But then $a_0$ must be an integer as well, since when you plug in a large number you will get an integer plus $a_0$.

share|cite|improve this answer
I don't see how you argue that $a_1=(\Delta f)(0)=f(1)-f(0)$ must be integer. – Marc van Leeuwen Oct 16 '12 at 14:19
$\Delta(f)$ is a polynomial of strictly smaller degree than $f$ which takes integer values for all sufficiently large integers, so it follows from the inductive hypothesis on the degree. – user29743 Oct 16 '12 at 17:38

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.