NTIC Solving Quadratic Congruences

Chapter 16 Solving Quadratic Congruences

We have been doing a lot of work until now with squares. It is almost time to see one of the great theorems of numbers, which gives us great insight into the nature of squares in the integer world – and whose easiest proof involves lattice points!

🔗

This theorem (Quadratic Reciprocity, in the next chapter) will come from our trying to find the solution to a useful general problem, which I like to think of as the last piece of translating high school algebra to the modular world. That is the task of solving quadratic congruences, the modular equivalent to the well-known quadratic equations.

🔗

Recall that a (single-variable) quadratic expression is one of the form

$ax^2+bx+c\text{,}$ and a quadratic equation would be of the form

$ax^2+bx+c=0\text{.}$ In high school, students worldwide typically use the so-called quadratic formula to solve this:

$\begin{equation*} x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}\text{.} \end{equation*}$

🔗

Indeed, this formula goes back in one form or another nearly four millennia (see the end of this article for just one reference to an Old Babylonian problem of this type).

🔗

Example 16.0.1.

The presence of the square root in the general formula does not mean every solution requires irrational numbers. Often there are solutions of simpler types.

We can solve $x^2-5x+4=0$ over the positive integers fairly easily, as

$\begin{equation*} x^2-5x+4=(x-4)(x-1)=0\text{ implies }x=4\text{ or }x=1\text{.} \end{equation*}$

The equation $4x^2+4x+1=0$ requires us to move to the rational numbers ( $\mathbb{Q}$ ), since

$\begin{equation*} 4x^2+4x+1=(2x+1)^2=0\text{ implies }2x+1=0\text{ so }x=-\frac{1}{2}\text{.} \end{equation*}$

On the other hand, sometimes we need to even go beyond the real numbers. The solutions of something like $x^2+5x+5=0$ will still be real, as the radical in the quadratic formula gives $\sqrt{5^2-4\cdot 1\cdot 5}=\sqrt{5}\text{.}$ But solving $x^2+5x+7=0$ requires

$\begin{equation*} \frac{-5\pm \sqrt{5^2-4\cdot 1\cdot 7}}{2\cdot 1}=-\frac{5}{2}\pm \frac{\sqrt{-3}}{2} \end{equation*}$

which only makes sense in the complex numbers $\mathbb{C}$ (recall Definition 14.1.2).

🔗

The previous example may be considered in a different way. Namely, for different number systems like

$\mathbb{Z}$ or

$\mathbb{R}\text{,}$ we may ask which quadratic expressions have a solution in the system. Then if we let a quadratic congruence be something of the form

$\begin{equation*} ax^2+bx+c\equiv 0\text{ (mod }n) \end{equation*}$

🔗

we can ask for which groups

$\mathbb{Z}_n$ there exists a solution!

🔗

Example 16.0.2.

Since $x^2-5x+4=(x-4)(x-1)\text{,}$ we should be able to solve it as a congruence for any $n\text{,}$ but we might wonder whether the other examples would have solutions always since they don't have integer solutions.

Consider $4x^2+4x+1\equiv 0\text{ (mod }5)\text{;}$ this is equivalent to $-x^2-x+1\equiv 0\text{,}$ and simple guess and check reveals that $x\equiv 2$ is a solution!

We leave it to the reader to check that $x^2+5x+5\equiv 0$ has a (very) simple solution if considered modulo $n=5\text{.}$ Perhaps most interestingly, $x^2+5x+7\equiv 0\text{ (mod }n)$ has solutions for no fewer than four different $n\lt 20\text{.}$ (See Exercise 16.8.1.)

🔗

This chapter will see how far we can extend all of these concepts to the modular world. We will begin by considering the notion of square root in that context.