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


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.