NTIC General Quadratic Congruences

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{.}\)

Algorithm 16.2.4. Completing the square modulo \(n\).

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

Multiply by four and \(a\text{:}\) \(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\text{.}\)

Fact 16.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)\text{.} \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.

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?

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.