# $2x^2 + 2x + 3 \equiv 0 \pmod{p}$ has at most two solutions for primes $\geq 5$

Does have at most 2 solutions for primes $p\geq 5$?

Mathematica confirms this for the first 10K primes:

Max[
Table[
Length[
Reduce[{
Mod[2*x^2 + 2*x + 3, Prime[i]] == 0, 0 <= x <= Prime[i]}, x,Integers]],
{i,3,10000}]
]

Output: 2


but I wasn't sure if it was true in general, and if it could be proved.

-
you're looking for roots of a quadratic polynomial in the field $\mathbb{F}_p$ - so surely there are at most 2 – user8268 Mar 29 '11 at 14:28
Don't call me Shirley – The Chaz 2.0 Mar 29 '11 at 15:16
Of course, you are talking about "at most 2 solutions" modulo $\mathbf{p}$. By the way, you don't need to check $x=Prime[i]$, since $0\equiv p\pmod{p}$; and you don't need to check $0$ except for $p=3$, where it is a solution. – Arturo Magidin Mar 29 '11 at 15:17

## 2 Answers

You are trying to find the roots of a polynomial over the field of $p$-elements.

Over any integral domain, in particular over any field, there are at most two solutions.

In particular, there are at most two solutions (modulo $p$ of course; if $a$ is a solution, then so is $a+kp$ for any integer $k$). This holds for all primes, not not just those greater than or equal to $5$.

In fact, you can do better and say exactly for which primes there are two solutions. The usual quadratic formula works (when correctly interpreted) for all primes other than $p=2$. The discriminant of this quadratic is $-20 = 4(-5)$. So for $p\neq 2$, the quadratic has:

• No solutions if $-5$ is not a square modulo $p$;
• One solution if $p=5$ (since the discriminant is $0$ in that case);
• Two distinct solutions (modulo $p$) if $-5$ is a square modulo $p$.

When $p=2$, there are no solutions (the quadratic reduces to $3\equiv 0\pmod{2}$). When $p=5$, the quadratic reduces to $2x^2+2x-2\equiv 0 \pmod{5}$, or $2(x^2+x-1) =2(x^2-4x+4) = 2(x-2)^2\equiv 0\pmod{5}$. The unique solution is $x\equiv 2 \pmod{5}$.

For other primes, we need to determine if $-5$ is a square. This is easily done with quadratic reciprocity. For $p=3$, $-5 \equiv 1\pmod{5}$, so it is a square, and we have two distinct solutions (they are $x\equiv 0 \pmod{3}$ and $x\equiv 2\pmod{3}$). If $p\gt 5$, We have (using the Legendre symbol and Quadratic Reciprocity and its supplements): $$\left(\frac{-5}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{5}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{p}{5}\right).$$ If $p\equiv 1\pmod{4}$, then $-1$ is a square modulo $p$, so $-5$ is a square if and only if $p$ is a square modulo $5$; that is, if $p\equiv 1,4\pmod{5}$. If $p\equiv 3\pmod{4}$, then $-1$ is not a square modulo $p$, so $-5$ is a square if and only if $p$ is not a square modulo $5$, that is, if $p\equiv 2,3\pmod{5}$.

So, there are two solutions modulo $p$ if and only if $p\equiv 1,3,7,9\pmod{20}$, and no solutions modulo $p$ if and only if $p\equiv 11,13,17,19\pmod{20}$.

In summary,

$2x^2 + 2x + 3 \equiv 0 \pmod{p}$, with $p$ a prime, has:

• No solutions if $p=2$, or if $p\equiv 11, 13, 17$, or $19\pmod{20}$.
• Exactly one solution modulo $p$ if $p=5$, namely $x\equiv 2 \pmod{5}$.
• Two distinct solutions modulo $p$ if $p\equiv 1 , 3, 7$ or $9\pmod{20}$; they are given by the quadratic formula modulo $p$.

How do you use the quadratic formula? The usual way. The roots are given by $$x = \frac{-2\pm\sqrt{-20}}{4} = \frac{-2\pm 2\sqrt{-5}}{4} = \frac{-1\pm\sqrt{-5}}{2}.$$ Given a prime $p$ for which $-5$ is a square, let $r$ be an integer such that $r^2\equiv -5\pmod{p}$. Let $s$ be an integer such that $2s\equiv 1\pmod{p}$ (say, $s=\frac{1-p}{2}$). Then the two solutions modulo $p$ are $x\equiv s(-1+r)\pmod{p}$ and $x=s(-1-r)\pmod{p}$.

-

Over any domain a polynomial has no more roots than its degree. The splitting behavior of your polynomial $\rm\:(mod\ p)\:$ depends only on the squareness $\rm\:(mod\ p)\:$ of the discriminant $-20\ =\: -5\cdot 2^2\:.\:$ By basic results on quadratic reciprocity we can analyse this behavior completely: for $\rm\:p=5\:$ it has $\:2\:$ as a double root; for odd $\rm\:p\equiv 1,3,7,9\ (mod\ 20)\$ it has two distinct roots; otherwise it is irreducible.

-