# Does there exist a finite set of polynomials which do not have roots over any prime field?

The polynomial $x^2 + 1$ has a root in $Z_p$ if and only if $p \not\equiv 3 \mod 4$, and the polynomial $x^2 + x + 1$ has a root in $Z_p$ if and only if $p \not\equiv 2 \mod 3$.

So each of the polynomials in the set $S = \{x^2 + 1, x^2 + x + 1 \}$ has roots in $Z_p$ if and only if $p \equiv 1 \mod 4$ and $p \equiv 1 \mod 3$.

Does there exist a finite set of polynomials with degree $\geq 1$ such that there is no $p$ such that each of the polynomials in the set has a root in $Z_p$?

This can be achieved with a countable, infinite set $S' = \{f_i(x) : f_i(x)$ is irreducible over $Z_{p_i}\}$ where $p_i$ is the $i$th prime.

Consider the set $S'' = \{2, 2x + 1 \}$
$2 \equiv 0 \mod p$ iff $p = 2$ and $2x + 1$ has a root iff $p \not= 2$.
Thus there is no $p$ such that all polynomials in the set have roots in $Z_p$.

Is there a way to get this property with a finite number of non-constant polynomials?

For example, can we find a polynomial, $g(x)$, such that $g(x)$ that has a root in $Z_p$ if and only if $p \equiv 2 \mod 3$?

We can reduce the cardinality of $S'$ by selecting polynomials which are irreducible for several prime fields, i.e. $x^2 + x + 1$ is irreducible over $Z_2, Z_5, ...$, so there exists a set, whose cardinality is strictly less than the cardinality of the set of primes, that achieves the property, but is it necessarily an infinite set?

• I bet there's a nice model theoretic proof that you can't have that. – Asaf Karagila Sep 23 '14 at 4:19

No. In fact, for any nonconstant (monic) polynomial $f$ with no repeated roots, we can find infinitely many primes $p$ such that $f(x)$ splits into linear factors $\bmod p$. In particular, we can take $f = \frac{f_1 f_2 \dots f_n}{\gcd((f_1 f_2 \dots f_n)', f_1 f_2 \dots f_n)}$ for any finite sequence $f_1, f_2, \dots f_n$ of (monic) irreducible polynomials (the denominator here just removes repeated factors). As with so many questions of this form, the key tool is a version of the Chebotarev density theorem; see this math.SE answer for some details.