Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Inspired by: Elementary proof that 2x^2+xy+3y^2 represents infinitely many primes?

share|improve this question
6  
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
3  
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
add comment

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}$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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