Generalizing Quadratic Formula to Modular Arithmetic

modular arithmeticquadratic-residuesquadratics

Does the quadratic formula $\displaystyle x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$ hold modulo $n$ for $ax^2 + bx + c \equiv 0 \pmod n$?

Computing the square root would require factoring $n$ and using either special-case formulas or the Tonelli-Shanks algorithm, but does the Quadratic Formula hold if used in this way? (For composite $n$, more than two square roots are possible, and that'd need to be accounted for.)

Best Answer

Yes, though it's not well-known (and despite incorrect claims to the contrary in other answers here) it is true that the quadratic formula (completing the square) can be used to solve modular quadratic equations in the way you envision, i.e. by viewing the square-root (and division or fractions) in the formula as multi-valued modular maps. Then - as classically - this allows us to use the formula to reduce solving modular quadratics to "simpler" normalized modular sub-problems of computing a square-root and division (or fraction). I describe this below for modular arithmetic (rings $\Bbb Z/n)$ but readers familiar with ring theory may observe that it works in any commutative ring where $\,2\ \&\ a\,$ are both cancellable (i.e. not zero-divisors), where $\,a\,$ is the lead coefficient.

As a motivating example, below we use this method to correctly do the example in Dan's answer. To make clear how the quadratic formula generalizes modularly, we show the full proof of the quadratic formula by $\color{#0a0}{\text{completing the square}}$ (specialized to this case). As in the OP, we assume that we have available an algorithm to compute modular square roots. Pay close attention to how the modulus changes throughout the process (clarified below).

$$\begin{align} x^2-5x+\,6&\,\equiv\, 0\pmod{\!1000}\\[.1em] \smash{\overset{\times\ 4}\iff}\ 4x^2\!-\!20x\!+\!24&\,\equiv\, 0\pmod{\!4000}\\[.1em] \iff\qquad\ \color{#0a0}{(2x\!-\!5)^2}\!&\,\equiv\, 1\pmod{\!4000}\ \ \ \ \color{#0a0}{\text{complete the }\square}\\[.1em] \iff\qquad\quad\! 2x-5\, &\,\equiv\, \pm\{1,751\}\qquad\ \pmod{\!2000}\\[.1em] \iff\qquad\qquad\quad\ x&\,\equiv\, \color{#c00}{(5\pm\{1,751\})/2}\!\!\!\pmod{\!1000}\\[.1em] \iff\qquad\qquad\quad\ x&\,\equiv\, 2,3,378,-373\ \pmod{\!1000} \end{align}\quad\ $$

We can view this as a quadratic "formula", $ $ i.e. $\, x\equiv \color{#c00}{\dfrac{5\pm\sqrt 1}2}\pmod{\!1000}\ $ iff we correctly view the square root and division maps as $\! $ multi-valued, $ $ and we use the correct modulus throughout. To avoid confusion, it is essential to keep in mind that the "formula" is a concise notation for the result we obtain by $\color{#0a0}{\text{completing the square}}$ - as above.

Note that the modulus $4000$ halves to $2000$ since if $\,r\,$ is a root of $\,x^2\equiv a\pmod{\!4n}\,$ then so too is $\,r\!+\!2n,\,$ by $\,(r\!+\!2n)^2 = r^2\!+\!4n(r\!+\!n)\equiv a\!+\!0.\,$ And it halves again from $2000$ to $1000$ due to the division by $2$, i.e. recall $\,2x\equiv 2a\pmod{\!2n}\iff x\equiv a\pmod{\!n}$.

For a general quadratic $\,ax^2+bx+c\,$ we scale by $\,4a\,$ (vs. $4$ above) when completing the square. So we divide by $2a$ (vs. $2$ above) by using general methods for solving modular linear congruences (or, equivalently, using multi-valued modular fractions - to enable a "formula" view), e.g.

$$\begin{align} 3x^2\,+\,x-4\ &\,\equiv\, 0\ \pmod{\!21}\\[.1em] \smash{\overset{\times\ 12}\iff}\ 36x^2\!+\!12x\!-\!48&\,\equiv\, 0\ \pmod{\!252}\\[.1em] \iff\qquad\ \ \ (6x\!+\!1)^2\! &\,\equiv\, 49\!\pmod{\!252}\\[.1em] \iff\qquad\quad\, 6x\!+\!1\,\ \ &\,\equiv\, \pm7\!\!\!\pmod{\!126}\\[.1em] \iff\qquad\qquad\quad\ \ \ x &\,\equiv\, 1\:\pmod{\!21} \end{align}\qquad\qquad$$

Compared to the more common method of factoring the modulus, then solving the quadratic mod prime powers, then combining the solutions using CRT, this method globally reduces the problem to root-taking and division, vs. that (or other methods) being applied locally mod $p^k$. It may save work by not having to repeat completing the square locally for each prime power, but that is traded off against the fact that there may be more efficient methods of solution after reducing mod $p^k$, e.g. in the prior example our quadratic $f$ reduces $\!\bmod 3\,$ to $\,x\!-\!1,\,$ and $\!\bmod 7\!:\ {-}2f\equiv(x\!-\!1)^2\,$ so the unique root $\,x\equiv 1\pmod{ \!3\ \&\ 7}\,$ lifts to a unique root $\!\bmod 21$ by CCRT (or we could notice the sum of the coef's $= f(1)= 0\,$ so $\,x=1\,$ is a root of $f,\,$ and the cofactor $f/(x\!-\!1) = 3x\!+\!4\!$ yields no more roots mod $3$ or $7)$.

Related Question