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