Our textbook states that the solvability of a general quadratic congruence of the form $ax^2 + bx + c \equiv 0\ (\textrm{mod} \ m)$ is equivalent to solvability of the binomial congruence $x^2 \equiv a\ (\textrm{mod}\ p)$ where $p$ is an odd prime and $gcd(a, p) = 1$. It later states that this follows from completing the square applied to procedures used in Hensel's lemma.

As I understand it, a quadratic congruence with generally non-prime modulus is equivalent to a system of quadratic congruences modulo $p_1^{k_1}$, $p_2^{k_2}$ and so on, not a single one. If we complete each of them to the square, we should obtain a system of congruences similar to:

$$x^2 \equiv d_1\ (\textrm{mod}\ p_1^{k_1}) \\ \vdots \\ x^2 \equiv d_n\ (\textrm{mod}\ p_n^{k_n})$$

where $d_i \not= a$ in general.

My main concern was whether the $a$ in the binomial congruence from our textbook is the coefficient of $x^2$ from the very first congruence or not. I am, however, missing also the part where the moduli are reduced to their first powers.

• The $a$'s mentioned in the statement are different. There is also some additional complication for even moduli, and for cases where the $a$ of $ax^2+bx+c$ is not relatively prime to $m$. – André Nicolas Mar 28 '15 at 15:48
• Is there somewhere the assumption that $m$ is odd? That simplifies things somewhat. – André Nicolas Mar 28 '15 at 16:10
• Oh, thank you. Of course, if a was not relatively prime to m, we could divide the congruence (modulus m too) by their greatest common divisor and thus convert it to that case, otherwise the congruence would not be solvable at all. And in what concerns even moduli m, this should be connected with Hensel's lemma and the derivative of $f(x) : x^2 - d_2$, but I think I am quite lost here. – Kyselejsyreček Mar 28 '15 at 16:11
• No, there is only a restriction that $p$ is an odd prime relatively prime to $a$. – Kyselejsyreček Mar 28 '15 at 16:14
• The dividing is quite a bit more subtle than in the linear case. I can give a simple answer in the case $m$ odd and relatively prime to the $a$ of $ax^2+bx+c$, and a more complicated answer for the general case. For the prime $2$, it is better not to think in terms of Hensel's Lemma. – André Nicolas Mar 28 '15 at 16:19

We give an analysis for $m$ odd and relatively prime to the $a$ of $ax^2+bx+c$, and then look briefly at the general case.
$1.$) Let $m$ be odd and relatively prime to $a$. The congruence $ax^2+bx+c\equiv 0\pmod{m}$ is equivalent to $$4a^2x^2+4abx+4ac\equiv 0\pmod{m},$$ which in turn is equivalent to $$(2ax+b)^2\equiv b^2-4ac\pmod{m}.$$ If $m=\prod p_i^{e_i}$, for any $i$ we solve the congruence $$y_i^2\equiv b^2-4ac\pmod{p_i^{e_i}}.$$ Let $y$ be any solution of the system $y\equiv y_i\pmod{p_i^{e_i}}$ (Chinese Remainder Theorem). Finally, we solve the linear congruence $2ax+b\equiv y\pmod{m}$.
$2.$ Now we take a brief look at the general case. Suppose $a\ne 0$. The congruence $ax^2+bx+c\equiv 0\pmod{m}$ is equivalent to the congruence $4a^2x^2+4abx+4ac\equiv 0\pmod{4am}$, which in turn is equivalent to $$(2ax+b)^2\equiv b^2-4ac\pmod{4am}.\tag{1}$$ Let $M=4am$, and let $\prod p_i^{e_i}$ be the prime power factorization of $M$. Then the congruence (1) is equivalent to the system of congruences $$(2ax+b)^2\equiv b^2-4ac\pmod{p_i^{e_i}}.$$ The problem reduces via the Chinese Remainder Theorem to solving $y_i^2\equiv b^2-4ac\pmod{p_i^{e_i}}$, and then solving the linear congruence $2ax+b\equiv y_i\pmod{p_i^{e_i}}$. There are complications when $\gcd(2a,p_i)\ne 1$.
• This was a great explanation, thank you! There's only a square power of $a$ missing right after multiplicating the general congruence by $4a$ in $4a^2x^2 + 4abx + 4c \equiv \pmod{m}$. – Kyselejsyreček Mar 28 '15 at 16:59
• Thank you for spotting the missing $^2$. – André Nicolas Mar 28 '15 at 19:20