Set of primes dividing polynomials and composition 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? 
 A: 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.
A: Edit: No; see Samir's answer.
The positive answer to your second question a related question (over any number field, not just $\mathbb{Q}$) is a theorem due to Bauer.  See Keith Conrad's notes on the History of Class Field Theory.
To apply Bauer's result, you need to know that Your $\mathcal{P}(A)$ is equal, up to a finite discrepancy, to the set of primes that split completely in the ring of integers of the splitting field of $A$ where the Frobenius element contains a 1-cycle.  The hypothesis of Bauer's theorem involves the set of primes where the Frobenius is the identity, i.e., those primes that split completely.  I can expand on this if you would like.
A: Here is a remark about Victor's modified question of what happens when $A$ is irreducible.  I'll show the following: given nonconstant $A,B\in\mathbf{Q}[x]$ with $A$ irreducible, the following are equivalent:


*

* there is a nonconstant $C\in\mathbf{Q}[x]$ for which $A\mid B\circ C$  


* there are roots $a$ of $A$ and $b$ of $B$ for which $\mathbf{Q}(b)\subseteq\mathbf{Q}(a)$.


It seems that the hypothesis
$\mathcal{P}(A)\subseteq\mathcal{P}(B)$ should connect more easily with the second condition than with the first, especially in light of Bauer's theorem.  I haven't had time to think about this though.
Here is the proof.  If $A\mid B\circ C$ then, for any root $a$ of $A$, we see that $C(a)$ is a root of $B$ which is contained in $\mathbf{Q}(a)$.  Conversely, if the second condition holds then $b$ is an element of $\mathbf{Q}(a)$, and hence can be written as $C(a)$ for some nonconstant $C(x)\in\mathbf{Q}[x]$.  Then $a$ is a root of $B\circ C$, so since $A$ is irreducible it follows that $A\mid B\circ C$.
