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

a x^{2} + b x + c,

and a quadratic equation would be of the form

a x^{2} + b x + c = 0 .

In high school, students worldwide typically use the so-called quadratic formula to solve this:

x = \frac{- b \pm \sqrt{b^{2} - 4 a c}}{2 a} .

🔗

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} - 5 x + 4 = 0$ over the positive integers fairly easily, as

x^{2} - 5 x + 4 = (x - 4) (x - 1) = 0 implies x = 4 or x = 1 .

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

4 x^{2} + 4 x + 1 = (2 x + 1)^{2} = 0 implies 2 x + 1 = 0 so x = - \frac{1}{2} .

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

\frac{- 5 \pm \sqrt{5^{2} - 4 \cdot 1 \cdot 7}}{2 \cdot 1} = - \frac{5}{2} \pm \frac{\sqrt{- 3}}{2}

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

🔗

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

Z

R,

we may ask which quadratic expressions have a solution in the system. Then if we let a quadratic congruence be something of the form

a x^{2} + b x + c \equiv 0 (mod n)

🔗

we can ask for which groups

Z_{n}

there exists a solution!

🔗

Example 16.0.2.

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

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

We leave it to the reader to check that $x^{2} + 5 x + 5 \equiv 0$ has a (very) simple solution if considered modulo $n = 5 .$ Perhaps most interestingly, $x^{2} + 5 x + 7 \equiv 0 (mod n)$ has solutions for no fewer than four different $1 < n < 20 .$ (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.

🔗

Summary: Solving Quadratic Congruences

This chapter continues discussion of quadratic entities, but returns to the context of solving congruences. Just like in high school algebra, one can move from solving linear to quadratic!

Section 16.1 continues our usual practice of review and exploration, this time by reminding us of many square roots modulo $n$ we have already found.
Next, we become systematic in finding an equivalent to the quadratic formula, by Completing the square modulo $n$ .
The next section introduces the important definition of quadratic residues in Definition 16.3.1, along with some examples and history.
It turns out that the set of (non-zero) quadratic residues for a given modulus is a group (Theorem 16.4.3), and we immediately use this in Fact 16.4.5 to characterize them in a way that we will use again and again.
We then reinterpret the middle column of Figure 16.5.1 as the incredibly useful Euler's Criterion.
The second-to-last section gives us a symbolic way to treat quadratic residues, via the Legendre symbol (Definition 16.6.1).
Finally, we bring all of this together in computing When Two is a Quadratic Residue.

The Exercises give a wide variety of practice, from solving full congruences to interesting theory and getting lists of residues.