# Prime Divisors of an Integer Polynomial

What is the proof that for any integer $n$ and any non-constant, integer coefficient polynomial $P(x)$, there are infinitely many primes congruent to $1 \pmod{n}$ that divide $P(x)$ for some $x$?

-
Neglecting the $p \equiv 1 \pmod{n}$ condition, here is a nice explanation of why there are infinitely many primes dividing $P(x)$ for some $x$. – Dan Brumleve Aug 21 '12 at 10:08

This is a pretty standard application of Cebatarov density: Let $K$ be the splitting field of $P(x)$. Let $L$ be the composite field of $K$ and $\mathbb{Q}(\zeta_n)$, where $\zeta_n$ is a primitive $n$-th root of unity. A prime $p$ splits in $K$ if and only if1 $P(x)$ splits into distinct linear factors modulo $p$; it splits in $\mathbb{Q}(\zeta_n)$ if and $p \equiv 1 \bmod n$; it splits in $L$ if and only if both are true. By Cebatarov density (or the weaker Theorem of Frobenius) the primes that split in $L$ have density $1/\dim L$.
1 With finitely many exceptions, related to the fact that the ring of integers in $K$ may not be $\mathbb{Z}[x]/P(x)$.
There is an elementary argument not using algebraic number theory as follows: If $f,g\in\mathbb Z[X]$ are non-constant polynomials, then there are infinitely many primes $p$ which divide some $f(a)$ and $g(b)$ for $a,b\in\mathbb Z$. Combine this with the other known elementary fact that the prime divisors of $\Phi_n(a)$ ($\Phi_n$ cyclotomic polynomial) divide $n$ or are $\equiv1\pmod{n}$. – Peter Mueller Dec 9 '15 at 16:48
@PeterMueller Do I understand right that the first statement is "the set of $p$ such that there exists $(a,b)$ with $p|GCD(f(a), g(b))$ is infinite"? How do you show that in an elementary way? – David Speyer Dec 9 '15 at 20:50
See Theorem 3 in projecteuclid.org/euclid.facm/1229442627. In even more down to earth terms: Let $\alpha$ and $\beta$ be roots of $f$ and $g$, respectively, $\mathbb Q(\gamma)=\mathbb Q(\alpha,\beta)$, and $h$ be the minimal polynomial of $\gamma$. There are polynomials $A$ and $B$ with $\alpha=A(\gamma)$, $\beta=B(\gamma)$. As $h$ is irreducible and $h(\gamma)=0=f(A(\gamma))$, we see that $h(X)$ divides $f(A(x))$ and $g(B(x))$. As $h(\mathbb Z)$ has infinitely many prime divisors, the assertion follows. – Peter Mueller Dec 9 '15 at 21:46
I see. The missing steps here are, since $f(A(\gamma)) = f(\alpha)=0$, we have $f(A(x)) = h(x) r(x)$ for some polynomial $r(x)$. Thanks! – David Speyer Dec 9 '15 at 21:50