Skip to main content
Logo image

Section 16.2 General Quadratic Congruences

The equation \(x^2+k\) is not the only quadratic game in town. What about other quadratics, such as \(x^2+2x+1\text{?}\) It turns out that we can use something you are already familiar with to reduce the whole game to the following.

Question 16.2.1.

For what primes \(p\) is there a solution to \(x^2\equiv k\text{ (mod }p)\text{?}\)
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)\text{.}\) The Sage function solve_mod works, if a little naively.

Sage note 16.2.2. Commands 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?

Subsection 16.2.1 Completing the square solves our woes

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

Example 16.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\text{,} \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\text{,}\) including of course \(n=9\text{,}\) with Sage.
Should you not have particularly enjoyed completing the square in the past, here is the basic idea for modulus \(n\text{.}\)

Example 16.2.6.

Let’s do all this with \(x^2+3x+5\equiv 0\) (mod \(n\)). Notice that \(b^2-4ac=9-20=-11\text{,}\) 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\text{,}\) though? Try some examples by hand before using the following interact.
In the previous example, note that we could not proceed as over the rational numbers by writing
\begin{equation*} x^2+3x+5=\left(x-\frac{3}{2}\right)^2+\left(5-\left(\frac{3}{2}\right)^2\right) \end{equation*}
since there is no element \(3/2\in \mathbb{Z}_n\text{;}\) this motivates part of the multiplication by \(4a\) in Algorithm 16.2.4. Also
I thank Zach Teitler for discussion on this point.
, note that if \(n=k\ell\) is composite and the quadratic reduces to a linear congruence modulo \(k\) or \(\ell\text{,}\) there may be solutions even if \(\gcd(2a,n)> 1\text{;}\) see Exercise 16.8.18.