Finding a prime $p$ to solve a quadratic congruence $\pmod{p}$

Question

I have a congruence of the form $$ax^2+bx \equiv -1 \pmod{p},$$ where $p$ is an odd prime and $a,b \in \mathbb{Z}$. Given $a$ and $b$, is there a general method to finding $p$ such that the above congruence holds?

Answer 1

The integers modulo a prime $p$, denoted ${\bf Z}/p{\bf Z}$, form a finite field (and to emphasize this it is also often denoted ${\bf F}_p$). Here, a quadratic $ax^2+bx+c$ has one root iff it has two roots (given one root, the other one can be computed as $b/a$ minus the first one).

The quadratic formula actually holds when $p\ne2$. Recall $\Delta=b^2-4ac$ is the discriminant.

$$au^2+bu+c=0\iff u=\frac{-b\pm\sqrt{\Delta}}{2a}.$$

Technically, $\sqrt{\Delta}$ by itself is ambiguous (it doesn't specify which square root), but with the $\pm$ there it should no longer matter. Thus, $ax^2+bx+c$ has a solution if and only if $\Delta$ is a square mod $p$, also known as a quadratic residue, which for $p\nmid\Delta$ can be expressed with the Legendre symbol

$$\left(\frac{\Delta}{p}\right)=1.$$

If you were going to do this for a specific $p$, you'd pick a residue of $\Delta$ mod $p$ and factor, then use multiplicativity. In general though you are correct that we need to factor $\Delta$ itself into a product of prime powers and $\pm1$. We can discard any squares that divide $\Delta$, so let $\Delta'$ be the radical of $\Delta$, and

$$\left(\frac{\Delta}{p}\right)=\left(\frac{\Delta' k^2}{p}\right)=\left(\frac{\Delta'}{p}\right)\left(\frac{k^2}{p}\right)=\left(\frac{\Delta'}{p}\right).$$

Thus it suffices to analyze $\Delta'$. In general, you need to look at the factorization of $\Delta'$ and invoke quadratic reciprocity, paying special care to $\Delta'$ being negative (I see this is what you were saying in the comments) and if it is even or odd.

---

Example: $\Delta'=-130$. For $p\ne 2,5,13$ we have $\displaystyle\left(\frac{\Delta}{p}\right)=1$ iff

$$1=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)\left(\frac{5}{p}\right)\left(\frac{13}{p}\right)\iff (-1)^{\Large \frac{p-1}{2}+\frac{p^2-1}{8}+\frac{5-1}{2}\frac{p-1}{2}+\frac{13-1}{2}\frac{p-1}{2}}=\left(\frac{p}{5}\right)\left(\frac{p}{13}\right).$$

The mod $8$ residues for which the power of $-1$ above yields $1$ are $p\equiv1,3$. The quadratic residues mod $5$ are $\pm1$, and the quadratic residues mod $13$ are $\pm1,\pm3,\pm4$. Therefore,

$$p\equiv\begin{cases} 1,3~(8) \\ \pm1~(5) \\ \pm1,\pm3,\pm4~(13)\end{cases}~{\rm or}~\begin{cases}1,3~(8) \\ \pm2~(5) \\ \pm 2,\pm5,\pm6~(13)\end{cases}~{\rm or}~\begin{cases}5,7~(8) \\ \pm1~(5) \\ \pm2,\pm5,\pm6~(13)\end{cases}~{\rm or}~\begin{cases}5,7~(8) \\ \pm2~(5) \\ \pm1,\pm3,\pm4~(13)\end{cases} $$

One may combine via Sun-Ze (aka Chinese Remainder Theorem) to find all $4\cdot2\cdot2\cdot6=96$ residues $r$ mod $2^3\cdot5\cdot13=520$ such that $p\equiv r~(520)$ implies $ax^2+bx+c$ has roots mod $p$, and the only exceptional cases not covered by these residues are $p=2,5,13$. ($\Delta\equiv0$ is a square mod $p$ so there is a root in those few cases.)