15
$\begingroup$

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

$\endgroup$
8
  • 4
    $\begingroup$ It works as long as everything exists. $(2a)^{-1} \pmod{n}$ has to exist and the square root has to exist. Either might not. $\endgroup$
    – B. Goddard
    Jun 7, 2022 at 22:00
  • 4
    $\begingroup$ The usual argument yields the usual formula, though of course $(2a)^{-1}\pmod n$ must exist and $\pm \sqrt k$ should be understood as "the set of solutions to $y^2\equiv k\pmod n$", if any. $\endgroup$
    – lulu
    Jun 7, 2022 at 22:06
  • 1
    $\begingroup$ @Joebloggs In modular arithmetic, a "perfect square" maps to the concept of "quadratic residue". (Naturally, when $s<n$ and $s$ is a perfect square, $s$ is definitely a quadratic residue mod $n$, but quadratic residues that aren't perfect squares usually exist.) $\endgroup$
    – Myria
    Jun 7, 2022 at 22:10
  • 2
    $\begingroup$ I think this is a great question. It touches on a lot of great things. I need to write out an full answer, but for now in an algebraically closed field such as $\mathbb{C}$, a square root of an element exists and there are exactly $2$ of them. In a field of characteristic $p$ prime not every element has a square so not every quadratic equations is solvable. In fact let $f$ be an irreducible polynomial in $\mathbb{F}_p$ of degree $d$ and $f$ could be degree $d=2$. Then $\mathbb{F}_p(\alpha)$ has $p^d$ elements where $\alpha$ is defined to be the root of $f$ in $\mathbb{F}_p$. $\endgroup$
    – Mike
    Jun 7, 2022 at 23:47
  • 2
    $\begingroup$ I expanded my answer and undeleted it, It explains how it is possible to to use the quadratic formula in the way you envision. $\endgroup$ Jun 9, 2022 at 5:44

3 Answers 3

9
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Where does the $751$ come from? $\endgroup$ Dec 4, 2022 at 7:13
  • 2
    $\begingroup$ @Dan It comes from taking the square root of the the prior congruence, using $\,z^2\equiv 1\pmod{\!4000}\iff z\equiv \pm\{1,751\} \pmod{\!2000},\,$ see the "Note" in the next paragraph. As I wrote, I am assuming one already knows how to compute modular square roots (which is discussed in other Q&As here). $\endgroup$ Dec 4, 2022 at 19:22
  • $\begingroup$ See this comment for another worked example. See also this answer, $\ \ $ $\endgroup$ Feb 27 at 20:04
6
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Neat explanation! So maybe so formula would work if we have $b= 2 b'$, and $a$ is invertible too? Although indeed the square root is a problem... $\endgroup$
    – orangeskid
    Jun 7, 2022 at 23:19
  • $\begingroup$ Does it work when division by $2a$ is defined ($\gcd(2a,n)=1$)? Also, when $n$ is prime, the number of roots is either $0$ or $2$. $\endgroup$
    – Myria
    Jun 7, 2022 at 23:24
  • $\begingroup$ Maybe it becomes a question of ruling out false positives then, something that does seem to crop up a lot in many different areas of maths. $\endgroup$
    – Joebloggs
    Jun 8, 2022 at 8:47
  • 4
    $\begingroup$ Beware that the conclusion is incorrect / misleading because the quadratic formula has not been properly generalized above. See my answer for one way to do that. Note also that the property that a nonzero polynomial over $D$ has no more roots in $D$ than its degree is a characteristic property of integral domains, so it is not reasonable to expect it may hold in rings not integral domains, e.g. $\,x^2 = 1\,$ has $4$ roots $\pm1,\pm3\,$ in $\,\Bbb Z_8 = $ integers $\!\bmod 8.\ \ $ $\endgroup$ Jun 9, 2022 at 5:58
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ It is not true that $2a$ must be a unit $\!\bmod n,\,$ e.g. $2$ is not a unit in the example in my answer. $\endgroup$ Jun 8, 2022 at 16:02
  • 5
    $\begingroup$ @Bill Dubuque: I did not say that it must be a unit, just that the usual formula will work if it IS a unit. And that you might encounter different kinds of trouble, that's best worked around by going mod $p^k$. $\endgroup$ Jun 8, 2022 at 16:07
  • $\begingroup$ The key point is how the usual quadratic formula (or its genesis - completing the square) needs modification to account for how constituent operations (roots and division) become multi-valued in more general rings, so restricting as you do to the "usual formula" misses the point. The second half of your answer does not apply to the question (and is a dupe of many other answers). $\endgroup$ Jun 8, 2022 at 16:14
  • 4
    $\begingroup$ @Bill Dubuque: You can of course bend the meaning of symbols to anything you like, and hide as much complexity behind them as you please. But at the end of the day, when it comes to actual computations, you'll have to discriminate cases and (powers of) prime factors. Completing the square already makes no sense if the equation decays to linear mod some divisor. And I don't understand why you are accusing me of duping when I just point out how to consistently solve the problem, while you only gave one example without explaining anything. $\endgroup$ Jun 8, 2022 at 16:34
  • 3
    $\begingroup$ Much of mathematics is about "bending the meaning of symbols" to find good generalizations. It's much better for site health to link to standard arguments rather than repeat them ad infinitum. When I have time I plan to expand my answer (I posted it quickly because a prior answer was misleading). $\endgroup$ Jun 8, 2022 at 16:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .