# Primes modulo which a given quadratic equation has roots

Given a quadratic polynomial $ax^2 + bx + c$, with $a$, $b$ and $c$ being integers, is there a characterization of all primes $p$ for which the equation $$ax^2 + bx + c \equiv 0 \pmod p$$ has solutions?

I have seen it mentioned that it follows from quadratic reciprocity that the set is precisely the primes in some arithmetic progression, but the statement may require some tweaking. The set of primes modulo which $1 + \lambda = \lambda^2$ has solutions seems to be $$5, 11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, \dots$$ which are ($5$ and) the primes that are $1$ or $9$ modulo $10$.

(Can the question also be answered for equations of higher degree?)

-

All but finitely many of the primes can be characterized by quadratic reciprocity. First handle the primes $p$ dividing $a$ (there is a solution if and only if $c \equiv 0 \bmod p$ or $b \not \equiv 0 \bmod p$). Next handle $p = 2$ (using the fact that $x^2 \equiv x \bmod 2$, so there is a solution if and only if $c$ is even or $a + b$ is odd).

For all remaining primes, complete the square to obtain $$\left( 2ax + b \right)^2 = b^2 - 4ac.$$

It follows that a solution exists if and only if $\left( \frac{b^2 - 4ac}{p} \right) = 1$, and the conditions for this to occur are given by quadratic reciprocity. (You get a congruence condition, but you also need to take into account all the primes dividing $b^2 - 4ac$.)

The situation for polynomials of higher degree is considerably more complicated (and I'll warn you in advance that I'm far from an expert in these matters, so take everything I say with a grain of salt). First, reduce WLOG to the irreducible case. If the Galois group of the polynomial is abelian, then by Kronecker-Weber the polynomial splits over some cyclotomic extension, so the way the polynomial factors modulo a prime is determined (again up to finitely many exceptions) by congruence conditions; this is all a part of the edifice of class field theory. I have been told that Artin reciprocity provides the appropriate generalization of quadratic reciprocity here but I don't know the details.

If the Galois group of the polynomial is non-abelian then the primes are not determined by congruence conditions. One can say some things about their statistical distribution using Chebotarev's density theorem but to actually characterize them is the subject of ongoing research and a part of what the Langlands program is supposed to do. At this MO question an example is given relating a specific modular form to roots modulo primes of the polynomial $x^3 - x - 1$ (or maybe the minimal polynomial of a primitive element of its splitting field instead).

-
Thanks! Could you elaborate on [the conditions for $\left( \frac{b^2 - 4ac}{p} \right) = 1$ are given by quadratic reciprocity]? Assuming $p$ does not divide $b^2 - 4ac$, how is it a congruence condition? – ShreevatsaR Mar 26 '12 at 7:07
@ShreevatsaR: factor $b^2 - 4ac$ into the greatest power of $2$ dividing it and its odd part. Use quadratic reciprocity on the first factor and Jacobi reciprocity on the second. You'll conclude that $\left( \frac{b^2 - 4ac}{p} \right)$ is a periodic function of $p$ with period something like $4p$. – Qiaochu Yuan Mar 26 '12 at 12:34

I never noticed this one before.

$$x^3 - x - 1 \equiv 0 \pmod p$$ has one root for odd primes $p$ with $(-23|p) = -1.$

$$x^3 - x - 1 \equiv 0 \pmod p$$ has three distinct roots for odd $p$ with $(-23|p) = 1$ and $p = u^2 + 23 v^2$ in integers.

$$x^3 - x - 1 \equiv 0 \pmod p$$ has no roots for odd $p$ with $(-23|p) = 1$ and $p = 3u^2 + 2 u v + 8 v^2$ in integers (not necessarily positive integers).

Here we go, no roots $\pmod 2,$ but a doubled root and a single $\pmod {23},$ as $$x^3 - x - 1 \equiv (x - 3)(x-10)^2 \pmod {23}.$$

Strange but true. Easy to confirm by computer for primes up to 1000, say.

The example you can see completely proved in books, Ireland and Rosen for example, is $x^3 - 2,$ often with the phrase "the cubic character of 2" and the topic "cubic reciprocity." $2$ is a cube for primes $p=2,3$ and any prime $p \equiv 2 \pmod 3.$ Also, $2$ is a cube for primes $p \equiv 1 \pmod 3$ and $p = x^2 + 27 y^2$ in integers. However, $2$ is not a cube for primes $p \equiv 1 \pmod 3$ and $p = 4x^2 +2 x y + 7 y^2$ in integers. (Gauss)

$3$ is a cube for primes $p=2,3$ and any prime $p \equiv 2 \pmod 3.$ Also, $3$ is a cube for primes $p \equiv 1 \pmod 3$ and $p = x^2 + x y + 61 y^2$ in integers. However, $3$ is not a cube for primes $p \equiv 1 \pmod 3$ and $p = 7x^2 +3 x y + 9 y^2$ in integers. (Jacobi)

-
Nice example, thank you. – ShreevatsaR Dec 14 '13 at 7:24