Section16.2General Quadratic Congruences¶ permalink

From the preceding section, it should be clear that, as far as just determining whether a solution exists, all we need to examine is prime moduli. Everything else is taken care of by previous work.

But it's not like \(x^2+k\) is the only quadratic game in town. What about other quadratics? It turns out that we can use something you are already familiar with to reduce the whole game to the following.

Question16.2.1

For what primes \(p\) is there a solution to \(x^2\equiv k\text{ (mod }p)\)?

Let's confirm this with a look at general quadratic congruences.

First let's try computing. As an example, take \(x^2-2x+3\text{ (mod }9)\). The Sage function solve_mod works, if a little naively.

Sage note16.2.2Commands of more sophistication

Notice that the solve_mod command is more complicated than divmod. solve_mod returns a list of tuples, where a tuple of length one has a comma to indicate it's a tuple. (If you tried to solve a multivariate congruence you would find it returns a longer tuple.)

The result shows that \(x^2-2x+3\equiv 0\) (mod \(9\)) has two solutions. But how might I solve a general quadratic congruence?

Subsection16.2.1Completing the square solves our woes

The key is completing the square! First let's do an example.

Example16.2.3

Completing the square for \(x^2-2x+3\) is done by \begin{equation*}x^2-2x+3=\left(x^2-2x+\left(\frac{2}{2}\right)^2\right)+3-\left(\frac{2}{2}\right)^2=(x-1)^2+2\, ,\end{equation*} so solving the original congruence reduces to solving \begin{equation*}(x-1)^2\equiv -2\text{ (mod }n)\end{equation*} Then assuming I have a square root \(s\) of \(-2\) (mod \(n\)), I just compute \(s+1\) and I'm done! Go ahead and try this for a few different \(n\), including of course \(n=9\), with Sage.

Should you not particularly enjoy completing the square, here is the basic idea.

Algorithm16.2.4Completing the square modulo \(n\)

To complete the square for \(ax^2+bx+c\equiv 0\), the key thing to keep in mind is that we do not actually divide by \(2a\), but instead multiply by \((2a)^{-1}\). Here are the steps.

Multiply by four: \(4a^2x^2+4abx+4ac\equiv 0\)
Factor the square: \((2ax+b)^2-b^2+4ac\equiv 0\)
Isolate the square: \((2ax+b)^2\equiv b^2-4ac\)

So to solve, we'll need that \(2a\) is a unit (more or less requiring that \(n\) is odd), and then to find all square roots of \(b^2-4ac\) in \(\mathbb{Z}_n\).

Fact16.2.5

The full solution to \begin{equation*}ax^2+bx+c\equiv 0\text{ (mod }n)\end{equation*} is the same as the set of solutions to \begin{equation*}x\equiv(2a)^{-1}(s-b)\text{ (mod }n)\text{, where }s^2\equiv b^2-4ac\text{ (mod }n)\end{equation*} Note that this means \(\gcd(2a,n)=1\) must be true and that \(s^2\equiv b^2-4ac\) must have a solution.

Example16.2.6

Let's do all this with \(x^2+3x+5\equiv 0\) (mod \(n\)). Notice that \(b^2-4ac=9-20=-11\), so this equation does not have a solution over the integers, or indeed over the real numbers. Does it have a solution in \(\mathbb{Z}_n\) for some \(n\), though?