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?

  • $\begingroup$ I bet there's a nice model theoretic proof that you can't have that. $\endgroup$ – 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.

(I need "monic" because that's what the version of the theorem that I could find requires, but I would be extremely surprised if this was essential.)

  • $\begingroup$ Lol, the only reason I didn't answer was because I was concerned about the "monic" property. But I, too, would be surprised if it mattered. For instance, Bjorn Poonen avoids it here mathoverflow.net/questions/15220/… but it hasn't occurred to me yet how. $\endgroup$ – Barry Smith Sep 23 '14 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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