# How to find all polynomials that map integers to integers?

How can one find all polynomials of degree k that map integers to integers? In other words, how to get all combinations of coefficients

$a_0,...,a_k \in \Bbb R$

sucht that

$n \in \Bbb Z \implies p_k(n) = \sum _{i=0}^{k} a_i n^i \in \Bbb Z$

?

For example $(n^2 + n)/2$ maps integers to integers and I think

$\{ p_2(n) \space | \space n \in \Bbb Z \implies p_2(n) \in \Bbb Z \} = \{q(n^2+2rn)/2 \space | \space q,r \in \Bbb Z\}$

• See also this. The link in Marty Cohen's answer is what you want I think. Well, lhf gives another way of looking at it. Oct 2 '17 at 16:40
• This is called an "arithmetic polynomial" IIRC, and probably many algebraic geometry textbooks for example would have a discussion of them. (There, they arise in the definition of the arithmetic genus of a projective scheme.) Oct 2 '17 at 19:26
• The book by Cahen, Chabert, Integer-valued polynomials, American Mathematical Society (1997) is related to your question. Oct 3 '17 at 12:22

Also $n\mapsto \binom{n}k$ is integer valued for each $k$, and so is any integer linear combination of these: $\sum_{k=0}^m a_k\binom{n}k$. Indeed these are all the integer-valued polynomials. The key to proving this is to note that if $f$ is integer-valued, then $n\mapsto f(n+1)-f(n)$ is also integer-valued.

• could you expand on how $f(n+1) - f(n)$ being integer helps? I dont get it Oct 2 '17 at 17:07
• Think about what this operation does to $f(n)=\binom nk$. Oct 2 '17 at 17:08
• @tobi303: What the answers haven't brought up is that the degree of the polynomial $f(x+1)-f(x)$ is at least one less than the degree of $f(x)$, enabling an inductive argument reducing to the base case of constant polynomials.
– user14972
Oct 3 '17 at 4:29
• @Hurkyl tbh I am not too much interested in a formal proof but mainly how those polynomial look like. In particular I find it interesting that the non-integer factor of a polynomial of degree $k$ is $1/k!$ which completely makes sense, as you need eg at least two terms in $\prod (n+o_i)$ to always get an integer that is divisible by two (in general at least $k$ terms get a result that is divisible by $k$). Oct 3 '17 at 17:34

Hint. A polynomial $P(x)$ always takes integer value iff

1. $P(0) \in \Bbb{Z}$.
2. $Q(x)$ always takes integer value, where $Q(x) = P(x) - P(x-1)$.