3
$\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
  • 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$ May 29, 2013 at 16:57

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .