Quadratic Equation Modulo an even composite

Question

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.

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.