• $\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.

  • $\begingroup$ Em. This will definitely take time for me to digest. How on earth did you manage to think about Newton's Interpolation Formula $\endgroup$ – crskhr Jun 10 '16 at 12:24
  • $\begingroup$ @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$?". $\endgroup$ – lhf Jun 10 '16 at 12:29
  • $\begingroup$ @S.C., for other applications of this technique, see 1, 2, 3. $\endgroup$ – lhf Jun 10 '16 at 12:35
  • $\begingroup$ 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. $\endgroup$ – crskhr Jun 10 '16 at 13:16
  • $\begingroup$ @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. $\endgroup$ – 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.)

  • $\begingroup$ 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?? $\endgroup$ – crskhr Jun 10 '16 at 11:37
  • $\begingroup$ 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. $\endgroup$ – John Hughes Jun 10 '16 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.