2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I might be missing something... but $11$ and $12$ are not solutions of the equation modulo $28$ (they both evaluate to $14$ under modulo). $\endgroup$ – Peter Košinár May 29 '13 at 16:57
2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Note: Those modulo $2^k$ cases also require Hensel lifting to find them. My answer basically tells how many there will be. $\endgroup$ – Jyrki Lahtonen May 30 '13 at 18:06

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.