[Introduction to Number Theory Series Part 19] What Do Quadratic Congruences and Quadratic Residues Show Us?

After congruence, inverses, linear congruences, and the Chinese remainder theorem, we are ready to move beyond linear problems.

What this post covers

• What a quadratic congruence is
• What a quadratic residue means
• A small example modulo 7
• Why this topic points toward deeper number theory

Key terms

• quadratic residue: a value that is congruent to a square modulo n
• congruence: the relation of equal remainders
• modular arithmetic: arithmetic in remainder classes
• prime number: a basic building block of integers

What changes in a quadratic congruence?

A linear congruence has the form

$$ax \equiv b \pmod n.$$

A quadratic congruence looks like

$$x^2 \equiv a \pmod n.$$

Now the question is different: can the target value be represented as a square modulo n?

What is a quadratic residue?

An integer a is called a quadratic residue modulo n if there exists an integer x such that

$$x^2 \equiv a \pmod n.$$

So the question is: which remainder classes appear as squares?

Example: squares modulo 7

Modulo 7, every integer is congruent to one of

$$0,1,2,3,4,5,6.$$

So it is enough to square these representatives. Once we know the square values of these seven classes, we know every possible square modulo 7.

• 0^2 \equiv 0
• 1^2 \equiv 1
• 2^2 \equiv 4
• 3^2 \equiv 9 \equiv 2
• 4^2 \equiv 16 \equiv 2
• 5^2 \equiv 25 \equiv 4
• 6^2 \equiv 36 \equiv 1

Therefore the quadratic residues modulo 7 are

$$0,1,2,4.$$

The values 3, 5, and 6 are not quadratic residues modulo 7.

Why is this interesting?

At first this may look like a table-making exercise, but it opens several deeper questions:

• Which values are squares modulo a prime?
• How many solutions can a quadratic congruence have?
• What patterns govern these square classes?

These questions lead into much deeper number theory.

Common mistakes

1. Expecting quadratic congruences to behave like linear ones

They are usually more subtle.

2. Focusing only on the table and missing the concept

The key question is not the list itself but which remainder classes are squares.

3. Assuming the same residues work for every modulus

Quadratic residue behavior depends strongly on the modulus.

Wrap-up

Quadratic residues show that congruence theory goes beyond linear equations. Even a simple-looking question like x^2 \equiv a \pmod n already leads into deeper structure.

In the final post, we step back and connect the whole series to algorithms, cryptography, and future study directions.