We all know that If $(a,m) = 1$ , Then the linear congruence $ax\equiv b(mod\ m)$ has exactly one solution. Can we conclude something similar for quadratic congruence $ax^{2}+bx+c\equiv 0(mod\ m)$ ( i.e. a condition on $a ,b ,c$ and $m$ such that it has $2$ solutions , since they always occur in pairs )?

  • $\begingroup$ The proper conclusion for quadratics is "at most two solutions"... $\endgroup$ – abiessu Jun 20 '17 at 15:40
  • $\begingroup$ @abiessu So $x^2-1\equiv0\pmod{15}$ has "at most two solutions"? $\endgroup$ – Lord Shark the Unknown Jun 20 '17 at 15:46
  • $\begingroup$ @LordSharktheUnknown: hmm, maybe I mixed up $m$ with a prime $p$... $\endgroup$ – abiessu Jun 20 '17 at 15:47

The quadratic formula works mod $m$ provided $2a$ is invertible mod $m$, that is, $\gcd(2a,m)=1$.

The discriminant $\Delta = b^2-4ac$ plays a similar role as in $\mathbb R$, that is, the equation $ax^{2}+bx+c\equiv 0 \bmod m$ has:

  • no solution, if $\Delta$ is not a square mod $m$

  • one solution, if $\Delta=0$

  • two or more solutions, if $\Delta$ is a square mod $m$

When $m$ is prime, then there are at most two solutions. This may fail when $m$ is composite. For instance, $x^2-1=0$ has four solutions mod $8$.

  • $\begingroup$ When $\gcd(2a,m)>1$, things are more complicated. $\endgroup$ – lhf Jun 20 '17 at 17:31

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.