Solvability of quadratic congruence

Question

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.

Thank you in advance.

Answer 1

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$.