Testing polynomial divisibility by evaluation at specific points

This question is just something I got to wondering about. Assume

$$p(x), q(x) \in \Bbb Z[x], \deg (q) = m \lt \deg(p) =n.$$

Assume also $$\forall a_k \in \{a_k~|~0 \leq k \leq n-m \} \subseteq \Bbb Z~ (\text{with } a_k \text{ distinct}), q(a_k)|p(a_k) \text{ in } \Bbb Z.$$

Does it follow that $$\exists k(x) \in \Bbb Q[x] \text{ such that } p(x)=k(x)q(x)$$?

If so, and if $$p$$ and $$q$$ are both monic, does it follow that $$k(x) \in \Bbb Z[x]$$?

In other words, can you test polynomial divisibility (in $$\Bbb Q[x]$$) by testing divisibility for $$n-m+1$$ witnesses?

Clearly that's enough witnesses to whittle yourself down to a single candidate for the quotient polynomial. But it's not obvious to me that this candidate must actually be the quotient.

This seems relatively basic but I don't think I've ever seen the question discussed.

No, this doesn't work. Consider $$p(x) = x^4 + 1$$ and $$q(x) = x^2 + 1$$. We have $$p(a) = q(a)$$ for $$a=0,\pm 1$$ but $$p$$ and $$q$$ have no roots in common over $$\mathbb{C}$$. In this example, it fails most obviously because the conditions on $$k(x)$$ determine it to have degree less than $$2$$.
But that's not the only thing that goes wrong. As another example, take $$p(x) = 3x^4+1$$ and $$q(x)=x^2+1$$. Now, $$q(\pm 1) = 2 | 4 = p(\pm 1)$$ and $$q(0) = 1 = p(0)$$. The conditions forced upon $$k(x)$$ are that $$k(\pm 1) = 2$$ and $$k(0)=1$$, which determines $$k(x) = x^2+1$$, which does not divide $$x^4+1$$.