For a non-constant polynomial $A \in \mathbb{Z}[x]$, let $\mathcal{P}(A)$ denote the set of prime numbers $p$ which divide $A(n)$ for some integer $n$. If $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ for some $A,B$, does there necessarily exist $C \in \mathbb{Q}[x]$ such that $A|B\circ C$? (Here, $B \circ C = B(C(x))$ is the usual polynomial composition). If so, is there an efficient way to find such $C$? This would provide a nice method to check, for example, if two polynomials have the same set of prime factors: if $A(x) = x^3 - 7x -7$ and $B(x) = x^3 + x^2 - 2x - 1$, we can take $C(x) = x^2 - x - 5$, and if we swap $A,B$, $C(x) = x^2 + 2x - 1$ works, proving that $\mathcal{P}(A) = \mathcal{P}(B).$ The question is whether there always exists such $C$. We can ask more: can we conclude from $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ that the splitting field of $A$ contains that of $B$ (over $\mathbb{Q}$)?


If the answer is negative, is there any nice way to characterize the counterexamples, or to find one with $A$ of minimal degree? 



Set of primes dividing polynomials and composition
I guess this answer complements Gene's answer above. Here is an example to think about. Let
$$
A=(x^2-2)(x^2-17)(x^2-34).
$$
It's an easy exercise in quadratic reciprocity to show that $\mathcal{P}(A)$ is the set of all primes. Let
$$
B=(x^2-2)(x^2-41)(x^2-82).
$$
In the same way $\mathcal{P}(B)$ is the set of all primes and so equals $\mathcal{P}(A)$. Now suppose $A \mid B \circ C$---we want a contradiction. It follows that $\sqrt{17}$ is a root of the polynomial
$$
(C(x)^2-2)(C(x)^2-41)(C(x)^2-82).
$$
So one of the following $\sqrt{2}$, $\sqrt{41}$, $\sqrt{82}$ belongs to $\mathbb{Q}(\sqrt{17})$ which is impossible.


