Given $n$ points prove there is a polynomial with integer coefficients…

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.

-
Are $x_k,y_k$ integers? –  user17762 Jan 8 '13 at 23:43
Would anything change if they weren't? –  Looft Jan 8 '13 at 23:43
Well. Yes. For instance if $p(1) = 1/2$, then clearly all the coefficients cannot be integers. –  user17762 Jan 8 '13 at 23:44
Then, I'll edit the question to make things clearer... –  Looft Jan 8 '13 at 23:45
I don't understand the question. There ARE polynomials with integer coefficients. They do exist. –  Git Gud Jan 9 '13 at 0:08

Hint: Note that if the polynomial $P(x)$ has integer coeffients, then $6-2$ divides $P(6)-P(2)$.
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? –  Looft Jan 9 '13 at 0:00
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? –  Looft Jan 9 '13 at 0:35
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 9 '13 at 0:53