2

For example if $p(x)$ is a polynomial of any degree and $p(x_1) = y_1$, $p(x_2) = y_2 \ldots$ where $x_k$ and $y_k$ are integers, how can I show that there is or there isn't a polynomial with integer coefficients going through the $n$ points?

$$p(2) = 4,~ p(6) = 6 ?$$

This was the original problem but I guess the general method is definitely sought for the answer.

1 Answers1

5

Hint: Note that if the polynomial $P(x)$ has integer coeffients, then $6-2$ divides $P(6)-P(2)$.

André Nicolas
  • 507,029
  • +1. Very nice hint. Is this also a sufficient condition? –  Jan 09 '13 at 00:00
  • So, what you're saying is that for $n$ points I would need to check $\binom{n}{2}$ statements of that form if I wished to give an answer to the problem? –  Jan 09 '13 at 00:00
  • I guess the sufficient condition would be that the divided difference are integers, which actually doesn't give much. –  Jan 09 '13 at 00:30
  • Is my understanding correct? $p(x1) - p(x2) = a_{n}(x_{1}^n - x_{2}^n) + a_{n-1}(x_{1}^{n-1} - x_{2}^{n-1}) + \ldots + a_{1}(x_{1} - x_{2})$. To me, it seems that the difference is divisible by $(x_{1} - x_{2})$ regardless of the coefficients? –  Jan 09 '13 at 00:35
  • Divisible algebraically, yes, but the quotient needn't be an integer. – Gerry Myerson Jan 09 '13 at 00:53
  • 1
    As a polynomial in two variables, yes. But that does not lead to any problem. There certainly is a polynomial with rational coefficients taking on any specified rational values $b_1,\dots,b_k$ at any specified points $a_1,\dots,a_k$. – André Nicolas Jan 09 '13 at 00:53
  • Well, that clears things up. Thank you! –  Jan 09 '13 at 01:08
  • Without restriction to integers, you might look up the Lagrange Interpolation Theorem on Wikipedia. – André Nicolas Jan 09 '13 at 01:16