Quadratic Residues Overview: Introductory Residue Theory

Welcome, students 🌟 This lesson introduces the basic idea behind residue theory, which is the language used to study numbers modulo $n$. You will learn how to talk about remainders, how residue classes work, and why this topic matters for quadratic residues. By the end of the lesson, you should be able to explain the main ideas of residues, use modular arithmetic to solve simple examples, and connect residue theory to the question of which numbers are squares modulo a given integer.

What is a residue?

A residue is just the remainder you get after dividing one integer by another integer. For example, when $17$ is divided by $5$, the remainder is $2$, so $17$ is congruent to $2$ modulo $5$. We write this as $17 \equiv 2 \pmod{5}$.

This idea is the foundation of residue theory. Instead of thinking only about exact numbers, we group integers by their remainders. If two integers leave the same remainder when divided by $n$, they belong to the same residue class modulo $n$.

For example, modulo $4$, the integers $1$, $5$, $9$, and $13$ all have remainder $1$. So they are all in the same residue class. This means that, in modulo arithmetic, these numbers behave the same way for many calculations.

A good real-world example is a clock 🕒. On a $12$-hour clock, after $12$ comes $1$ again. This is modular arithmetic with modulus $12$. If it is $10$ o’clock now and $5$ hours pass, the new time is $3$ o’clock because $10 + 5 = 15$ and $15 \equiv 3 \pmod{12}$.

Congruence and residue classes

The main notation in residue theory is congruence. We say that $a \equiv b \pmod{n}$ if $n$ divides $a-b$. This means $a$ and $b$ have the same remainder when divided by $n$.

Let’s unpack that with an example. Since $23 - 8 = 15$ and $15$ is divisible by $5$, we have $23 \equiv 8 \pmod{5}$. Also, $23$ and $8$ both leave remainder $3$ when divided by $5$.

A residue class modulo $n$ is the set of all integers congruent to a particular number modulo $n$. For modulus $6$, the residue classes are:

$[0] = \{\dots,-12,-6,0,6,12,\dots\}$
$[1] = \{\dots,-11,-5,1,7,13,\dots\}$
$[2] = \{\dots,-10,-4,2,8,14,\dots\}$
and so on up to $[5]$

There are exactly $n$ residue classes modulo $n$. Every integer belongs to one of them. This is important because it lets us reduce large numbers to simpler representatives without losing the modular information.

For example, to compute $278 + 346 \pmod{7}$, we may reduce first:

$278 \equiv 5 \pmod{7}$ and $346 \equiv 3 \pmod{7}$.

Then

$278 + 346 \equiv 5 + 3 \equiv 8 \equiv 1 \pmod{7}$.

So the answer is $1$ modulo $7$.

Why residue theory matters for squares

Now let’s connect residue theory to quadratic residues. A quadratic residue modulo $n$ is a number that is congruent to a perfect square modulo $n$. In other words, a number $a$ is a quadratic residue modulo $n$ if there exists an integer $x$ such that $x^2 \equiv a \pmod{n}$.

This idea depends completely on residue classes. Instead of asking whether a number is literally a square, we ask whether it behaves like a square after taking remainders modulo $n$.

For example, modulo $7$, the squares are:

$0^2 \equiv 0 \pmod{7}$

$1^2 \equiv 1 \pmod{7}$

$2^2 \equiv 4 \pmod{7}$

$3^2 \equiv 9 \equiv 2 \pmod{7}$

$4^2 \equiv 16 \equiv 2 \pmod{7}$

$5^2 \equiv 25 \equiv 4 \pmod{7}$

$6^2 \equiv 36 \equiv 1 \pmod{7}$

So the quadratic residues modulo $7$ are $0$, $1$, $2$, and $4$. The nonresidues are $3$, $5$, and $6$.

This shows how residue theory helps us classify numbers. We do not need to compute huge squares exactly; we only need their remainders.

A simple pattern appears for prime moduli like $7$. The nonzero squares modulo a prime $p$ come from the numbers $1,2,\dots,p-1$, but some remainders repeat. For a prime $p$, there are exactly $\frac{p-1}{2}$ nonzero quadratic residues modulo $p$.

Working with residue calculations

Residue theory becomes powerful because arithmetic respects congruence. If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then:

$ a + c \equiv b + d \pmod{n}$

$ a - c \equiv b - d \pmod{n}$

$ ac \equiv bd \pmod{n}$

This means we can simplify computations by replacing numbers with smaller equivalent residues.

Example: determine whether $11^2$ is a quadratic residue modulo $8$.

First compute the remainder of $11$ modulo $8$:

$11 \equiv 3 \pmod{8}$.

Then

$11^2 \equiv 3^2 \equiv 9 \equiv 1 \pmod{8}$.

So $11^2$ is congruent to $1$ modulo $8$, and $1$ is certainly a quadratic residue modulo $8$ because $1^2 \equiv 1 \pmod{8}$.

Another example: is $3$ a quadratic residue modulo $8$? Check all squares modulo $8$:

$0^2 \equiv 0$

$1^2 \equiv 1$

$2^2 \equiv 4$

$3^2 \equiv 1$

$4^2 \equiv 0$

$5^2 \equiv 1$

$6^2 \equiv 4$

$7^2 \equiv 1$

The only residues that appear are $0$, $1$, and $4$. So $3$ is not a quadratic residue modulo $8$.

This kind of checking is the first step in residue theory: list the possible residues, then see which ones occur.

Introducing the Legendre symbol

When the modulus is an odd prime $p$, there is a compact way to describe whether a number is a quadratic residue: the Legendre symbol. It is written as $\left(\frac{a}{p}\right)$.

Its meaning is:

$\left(\frac{a}{p}\right) = 1$ if $a$ is a quadratic residue modulo $p$ and $p \nmid a$
$\left(\frac{a}{p}\right) = -1$ if $a$ is a nonresidue modulo $p$
$\left(\frac{a}{p}\right) = 0$ if $p \mid a$

This symbol is a shorthand, not a fraction in the ordinary sense.

Example: modulo $7$, we found that $2$ is a quadratic residue because $3^2 \equiv 2 \pmod{7}$. So $\left(\frac{2}{7}\right) = 1$.

Also, $3$ is not a quadratic residue modulo $7$, so $\left(\frac{3}{7}\right) = -1$.

The Legendre symbol is useful because it lets mathematicians talk about quadratic residue questions efficiently. It also helps express patterns such as multiplicativity:

$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

for an odd prime $p$ and integers $a$ and $b$.

This property comes directly from residue theory, since products of squares are still squares modulo $p$.

A closer look at introductory residue theory

Introductory residue theory is really about three connected ideas: remainders, equivalence classes, and arithmetic with congruences. These ideas let us organize large sets of integers into manageable groups.

One major benefit is that residue theory makes pattern-finding possible. For example, to understand which numbers are squares modulo $p$, we only need to test the finite list $0^2, 1^2, 2^2, \dots, (p-1)^2$ modulo $p$. Even though there are infinitely many integers, there are only finitely many residues.

This finiteness is what makes the theory so useful in number theory. Instead of searching forever, we study structure.

Here is a quick example of how residue classes simplify a problem. Suppose we want to know whether $45$ is a quadratic residue modulo $11$. First reduce $45$:

$45 \equiv 1 \pmod{11}$.

Since $1 = 1^2$, we know $45$ is a quadratic residue modulo $11$.

Notice how we did not need to work with $45$ directly. Residue theory allowed us to replace it with the much simpler number $1$.

Conclusion

Residue theory is the language of remainders modulo $n$, and it is the starting point for understanding quadratic residues. By grouping integers into residue classes, we can simplify arithmetic, detect patterns, and study squares modulo a number. The Legendre symbol extends this idea for odd primes by giving a compact notation for “square,” “not a square,” or “divisible by the prime.” students, this foundation will help you read more advanced results in quadratic residues and see how number theory turns big problems into manageable modular patterns 🔍

Study Notes

A congruence like $a \equiv b \pmod{n}$ means $n$ divides $a-b$.
A residue class modulo $n$ is the set of all integers with the same remainder when divided by $n$.
There are exactly $n$ residue classes modulo $n$.
Residue theory lets us replace large numbers with smaller equivalent ones in modular calculations.
A quadratic residue modulo $n$ is a number congruent to a perfect square modulo $n$.
To test quadratic residues, list the possible square remainders modulo $n$.
For an odd prime $p$, the Legendre symbol $\left(\frac{a}{p}\right)$ equals $1$, $-1$, or $0$ depending on whether $a$ is a residue, nonresidue, or divisible by $p$.
The multiplicative rule $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ helps simplify residue questions.
Residue theory is the foundation for the broader study of quadratic residues in number theory.