Can we generalize the quadratic formula to modular arithmetic?

Question

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

Answer 1

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

Answer 2

Consider a concrete example: $x^2-5x+6=0\ (\operatorname{mod} 1000)$

A brute-force search gives the integer solution set $x \in \lbrace 2, 3, 378, 627 \rbrace\ (\operatorname{mod} 1000)$.

The Quadratic formula gives you:

$$x = \frac{5 \pm \sqrt{1}}{2}$$

If you define $\sqrt{1}$ to mean any number $r$ such that $r^2 = 1\ (\operatorname{mod} 1000)$, then you get 8 possible integer values:

$\sqrt{1} \in \lbrace 1, 249, 251, 499, 501, 749, 751, 999 \rbrace$

Note the symmetry here: For every $r$, its additive inverse $-r = 1000 - r$ is also in the set. So we can ignore the $\pm$ notation and just use $+$. Anyhow, from this set, we get:

$$5 \pm 1 \in \lbrace 4, 6, 254, 256, 504, 506, 754, 756 \rbrace$$

We need to multiply each of these values by $\frac{1}{2}$. And by $\frac{1}{2}$, I of course mean a number $q$ such that $2q = 1\ (\operatorname{mod} 1000)$. There are no integer solutions, but if you allow rational solutions, then $q \in \lbrace \frac{1}{2}, 500+\frac{1}{2} \rbrace$.

So, if we take each the 8 possible values for $5 \pm 1$, multiply them by each of the two possible values for $\frac{1}{2}$, reduce the products modulo 1000, and ignore duplicates, we get:

$$x \in \lbrace 2, 3, 127, 128, 252, 253, 377, 378 \rbrace$$

Well, that does give three correct answers (2, 3, and 378), but it also gives five extraneous answers, and misses a valid answer (627). Maybe it would work better if 1 ÷ 2 had an integer solution, but it didn't.

So, I'm going to say no, the Quadratic Formula doesn't hold modulo $n$.

Even if it did “work” somehow, we'd lose the Fundamental Theorem of Algebra. With regular quadratic polynomials, we know that they always have two roots. Maybe they're not distinct, not rational, or not real, but there are two of them. With modular arithmetic, who knows how many roots there are?

Answer 3

You'll$\def\mod{\text{ mod }}$ get all solutions to $ax^2+bx+c = 0 \mod n$ by means of $x = \dfrac{-b +\sqrt{b^2-4ac}}{2a}, \tag 1$ provided that

• $\sqrt{r}$ is understood as the set of all solutions of $r^2=0\mod n$ and $(1)$ is understood as a set, and

• $2a$ is a unit in $\Bbb Z / n\Bbb Z$, i.e. $\gcd(2a,n) = 1$.

The interesting case is therefore if $2a$ is not a unit. In that case, write out what the quadratic equation actually means:

$ax^2+bx+c = kn \qquad\text{ for some } k\in\Bbb Z.\tag 2$

Now if $d=\gcd(a,b,c,n)\neq1$ we can divide $(2)$ by $d$ without changing the set of solutions. However, this won't fix that we still might have $\gcd(2a,n)\neq1$ after division. Handling this case is no fun, because the equation might behave differently for different prime divisors of $n$. For example, the equation might be quadratic modulo one prime and linear modulo some other prime.

To make a long story short, using $(1)$ directly $\mod n$ doesn't simplify the task, in particular because we have to factor $n$ anyway$^1$ in order to compute square roots modulo $n$. That said, the most generic and clean approach is:

1. Factorize $n$

2. For each prime $p|n$, determine all solutions mod $p$. Notice that the equation might decay into a linear one, or that each $x\in\Bbb Z/p\Bbb Z$ might solve the equation.

3. For each $p$, lift solutions $\mod p\to \mod p^2\to\cdots\to \mod p^{k_p}$ where $k_p$ is the order to which $p$ divides $n$. To that end, use the quadratic equation in the form $(2)$: If $x$ solves $(2)$ mod $p^j$, then solutions mod $p^{j+1}$ have the form $x'=x+\alpha p^j$. Hence, drop $x'$ into $(2)$ mod $p^{j+1}$ and determine $\alpha$. In most cases, this will double the number of solutions, i.e. you'll find more than one $\alpha$.

4. Using the Chinese Remainder Theorem, combine solutions mod $p^{k_p}$ to solutions$^2$ mod $n$.

---

$^1$Except you prefer to brute force, but then you don't need formulae like $(1)$ to begin with.

$^2$If $\#m$ denotes the number of solutions mod $m$, then $\displaystyle\#n=\prod_{p\mid n} \#(p^{k_p})$