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.

Using the quadratic formula, we have either 0, 1, or 2 solutions. I wonder if we could use it this formula for congruence? Or is there a formula to solve quadratic equation for congruence?

Edit Assume that $ax^2 + bx + c \equiv 0 \pmod{p}$, where $p$ is prime with $(a, p) = 1$, then is there a formula for this equation?

Thanks,

share|improve this question
3  
Yes: if $p\gt 2$, then you can just use the quadratic formula, suitably interpreted: "dividing" by $2a$ means multiplying by the modular inverse of $2a$ modulo $p$; and $\sqrt{b^2-4ac}$ means any modular class whose square is congruent to $b^2-4ac$ modulo $p$, if such exists. If there is no such modular class, then the quadratic is irreducible modulo $p$. If $p=2$, then you get no solutions if all of $a$, $b$, and $c$ are odd; you get a single double solution $x=1$ if $a$ and $c$ are odd, $b$ even; both $x=0,1$ if $b$ odd, $c$ even; and a single double $x=0$ solution if $b,c$ even. –  Arturo Magidin Apr 4 '11 at 2:44
    
@Arturo Magidin: Thank you. I got it. –  Chan Apr 4 '11 at 2:55
    
Regarding the modulus $\rm\:p=2\:$ see the Parity Root Test. –  Bill Dubuque Apr 4 '11 at 3:42

3 Answers 3

up vote 4 down vote accepted

If $n = p$ is prime, the situation is straightforward. When $p = 2$ there are a small number of cases, and when $p > 2$ the quadratic formula holds. (Note that the quadratic formula fails when $p = 2$ because you can't divide by $2$. This is because you can't complete the square $\bmod 2$.)

If $n$ is composite, the situation is more complicated. $x$ is a solution if and only if $x$ is a solution $\bmod p^k$ for every prime power factor of $n$ by the Chinese Remainder Theorem, so in particular if, say, $n$ is a product of $k$ distinct primes there can be as many as $2^k$ solutions obtained by combining roots modulo the prime factors of $n$.

After the above step the problem reduces to the prime power case $n = p^k$. In this case the question of what solutions look like is completely answered by Hensel's lemma. Again the case $p = 2$ is special.

share|improve this answer
    
@Quiaochu Yuan: Thank you. How about if $(a, p) = 1$, is it a special case? –  Chan Apr 4 '11 at 2:35
1  
@Chan: if $p > 2$ and $n = p^k$ then each solution $\bmod p$ can be uniquely extended to a solution $\bmod n$ by Hensel's lemma. If $p = 2$ then I think one needs to look at solutions $\bmod 8$. –  Qiaochu Yuan Apr 4 '11 at 2:38
    
@Chan: Did you mean $(a,p)=p$? When $(a,p)=1$, you are in the "easy" case, because $a$ is invertible modulo $p$ so you can divide by $2a$. –  Arturo Magidin Apr 4 '11 at 2:38
    
@Quiaochu Yuan: Thank you. –  Chan Apr 4 '11 at 2:53
    
@Arturo Magidin: I meant $(a, p) = 1$. I remember now, the "invertible part". Many thanks ;) –  Chan Apr 4 '11 at 2:54

The quadratic formula works just as well modulo n as long as $(2a,n) = 1$ and $b^2-4ac$ is a quadratic residue mod n. If either of those conditions do not hold, then there are no solutions.

Edit: as pointed out in the comments, this is not a complete answer; see Qiaochu Yuan's for a much better one.

share|improve this answer
1  
@Harry Stern: Thank you. That was exactly what I thought initially. –  Chan Apr 4 '11 at 1:54
    
@Chan I'm glad I could be helpful! –  Harry Stern Apr 4 '11 at 2:00
    
@Harry: That's false, e.g. $\rm\ m\ n\ x^2 + x\ $ has root $\rm x = 0\ (mod\ n)\ $ and $\rm\ (2a,n) = (2\ m\ n,\ n) = n > 1\:$ for $\rm\:n>1\:.$ Also there can be arbitrarily many roots for composite $\rm\:n\:.$ –  Bill Dubuque Apr 4 '11 at 2:02
    
@Harry Stern: It is absolutely helpful. Great thanks ;) –  Chan Apr 4 '11 at 2:02
1  
This answer is incomplete when $n$ is composite. As Bill Dubuque says, there can be arbitrarily many roots for composite $n$ because we can combine pairs of roots modulo the prime factors of $n$ by CRT. –  Qiaochu Yuan Apr 4 '11 at 2:12

Here (link) is a thorough discussion of the steps in reducing general moduli quadratic equation problems to those of prime moduli, including the case $p=2$.

share|improve this answer

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.