If $d=\gcd\,(f(0),f(1),f(2),\cdots,f(n))$ then $d|f(x)$ for all $x \in \mathbb{Z}$

• $\textbf{Question.}$ Let $f$ be a polynomial of degree $n$ which takes only integral values. If $d=\gcd\,\{f(0),f(1),f(2),\cdots,f(n)\}$ then show that $d|f(x)$ for all $x \in \mathbb{Z}$.
• How can one show this. It's clear that if $f$ has degree $1$, then $f(x)=a_{0}+a_{1}x$. Clearly we have $d|a_{0}$ and $d|a_{0}+a_{1}$ so we have $d\mid a_{1}$, this says $d\mid f(x)$ for all $x \in\mathbb{Z}$. So if $f$ has degree $1$, then I am able to prove the question.

• Now if I take a polynomial of degree $2$, says $f(x) = ax^{2}+bx+C$ then I get the following. $d|c$, $d|a+b+c$ and $d|4a+2b+c$. So we get $d|a+b$ which says $d|2a+2b$ which along with $d|4a+2b$ gives $d|2a$. Similarly $d|2b$. I am done if I am able to show $d|a$ and $d|b$ but I am not able to deduce that.

An elaborate solution would be helpful.

Note that $d$ divides $\gcd(f_0,f_1,f_2)$ iff $d$ divides $f_0,f_1,f_2$. (I'm using $f_k=f(k)$ for simplicity.)

Using repeated differences we get $$\begin{array}{lll} f_0 & f_1 & f_2 & \\ f_1-f_0 & f_2-f_1 \\ f_2-2f_1+f_0 \\ 0 \\ \end{array}$$ Newton's interpolation formula then gives us $$f(n) = f_0 \binom{n}{0} + (f_1-f_0) \binom{n}{1} + (f_2-2f_1+f_0) \binom{n}{2}$$ Therefore, if $d$ divides $f_0, f_1, f_2$, then $d$ divides $f(n)$ for all $n$. (And conversely, of course.)

In the general case, $$f(n) = d_0 \binom{n}{0} + d_1 \binom{n}{1} + d_2 \binom{n}{2} + d_3 \binom{n}{3} +\cdots$$ where $d_i$ are the numbers in the first column of the repeated differences array. It is clear that the $d_i$ are integer linear combinations of the $f_i$ and so if $d$ divides all $f_i$ then $d$ divides all $d_i$ and so all $f(n)$.

BTW, Newton's interpolation formula also proves that a polynomial takes integral values at integers iff it is an integer linear combinations of the binomial polynomials. See Integer-valued polynomial.

• Em. This will definitely take time for me to digest. How on earth did you manage to think about Newton's Interpolation Formula – crskhr Jun 10 '16 at 12:24
• @S.C., it's my favorite technique, the first one I learnt as a child, in the context of questions like "what is the next term in the sequence $12,45,78, \ldots$?". – lhf Jun 10 '16 at 12:29
• @S.C., for other applications of this technique, see 1, 2, 3. – lhf Jun 10 '16 at 12:35
• Em. In G.Polya's words "a trick that has been used twice becomes a technique" :P. Nice and thanks for the link. Once I understand the answer I will accept it. – crskhr Jun 10 '16 at 13:16
• @S.C., it is instructive to see $(d_0, d_1, \ldots)$ as the coordinates of $f$ in the binomial basis and $(f_0, f_1, \ldots)$ as the coordinates of $f$ in the Lagrange basis. Then the matrix that relates those coordinates is an integer triangular matrix having $1$ in the diagonal and so is invertible with an integer inverse. – lhf Jun 10 '16 at 15:10

Hint: You're doing pretty well. But so far, you've worked with the assumption that $d$ divides $f(0), f(1), f(2)$ in the quadratic case. But what's given is that it divides the gcd of these items.

You've never used the "gcd" part.

You might want to think about that a little while in hopes of getting the quadratic case to work out, at which point the more general case may seem more obvious.

(Yes, I know you asked for a completely elaborated solution, but I've chosen only to write this hint.)

• Thanks for the hint. No problem. I will try thinking. And if it doesn't strike, then i will always feel free to ask, and request for a detailed answer :D. One more thing : Is this the way for proving the general case as well. Say for degree "n" or something?? – crskhr Jun 10 '16 at 11:37
• I suspect that once you work out that degree 1, 2, and 3 cases, you'll be well on your way to generalizing. But I haven't done it myself, so I can't really say. – John Hughes Jun 10 '16 at 11:56