Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$.

I can think of ways to make various parts of this argument more elementary, but I don't see how to get away from using algebraic number theory; I'd be curious to see an elementary proof.

1 With finitely many exceptions, related to the fact that the ring of integers in $K$ may not be $\mathbb{Z}[x]/P(x)$.

share|cite|improve this answer
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 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.