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.

I am familiar with using the quadratic formula and Tonelli-Shanks with Hensel's Lifting Lemma to solve a quadratic equation, but how do I solve a quadratic equation in an even modulus? I can't use the quadratic formula because of the division by two. Would it be sufficient to multiply both sides of the equation (including modulus) by 2?

In particular, if I try to solve:

$x^2 + bx + c\equiv 0 \ (mod\ 2pq)$, where $p\equiv q\equiv 1\ (mod\ 2)$

I would end up with:

$\frac{-b \pm \sqrt{b^2-4c}}{2} \equiv 0\ (mod\ 2pq)$
$= -b \pm \sqrt{b^2-4c} \equiv 0\ (mod\ 4pq)$

does this work? Or am I terribly, terribly wrong?

edit: To start with a simple one: $x^2 + 5x + 6 \equiv 0\ (mod\ 28)$ the solutions are: $\{5,18,25,26\}$ I was able to find them using the quadratic formula without the division by 2 and then testing both possible solutions to the multiplicative inverse of 2 from the results there. However, I wasn't able to determine a pattern between finding those solutions and testing them versus checking the equation mod 56 either.

edit: corrected the solution set for the example.

share|improve this question
1  
I might be missing something... but $11$ and $12$ are not solutions of the equation modulo $28$ (they both evaluate to $14$ under modulo). –  Peter Košinár May 29 '13 at 16:57
    
Thanks, Peter, I've corrected the error. –  Foo Barrigno May 31 '13 at 11:04

1 Answer 1

Here is a quick recipe:

  1. Do it with one prime power factor of the modulus at a time.
  2. For an odd prime power modulus you can use the quadratic formula and Hensel lifting.
  3. When the modulus is a power of two, you can use this question and its answer.
  4. In the end you can combine the solutions modulo different prime powers by an application of the Chinese Remainder Theorem.
share|improve this answer
    
Note: Those modulo $2^k$ cases also require Hensel lifting to find them. My answer basically tells how many there will be. –  Jyrki Lahtonen May 30 '13 at 18:06

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.