Squares modulo $n$ 🔢

Welcome, students. In this lesson, you will learn how to study numbers made by squaring integers and then taking the remainder after division by a positive integer $n$. This topic is a core part of quadratic residues, which is one of the most important ideas in number theory.

What you will learn

By the end of this lesson, you should be able to:

explain what it means for a number to be a square modulo $n$
decide whether a number is a square modulo $n$ using examples and reasoning
connect squares modulo $n$ to quadratic residues and the Legendre symbol
describe why this topic matters in broader number theory and cryptography 🔐

Why this matters

When you square whole numbers, the answers look familiar: $0, 1, 4, 9, 16, 25, \dots$. But in modular arithmetic, the pattern changes in interesting ways. For example, modulo $5$, the squares are not all numbers. Some remainders appear, and some never do. Understanding which remainders can come from squares helps us solve equations like $x^2 \equiv a \pmod n$ and builds the foundation for more advanced topics.

What does “square modulo $n$” mean?

A number $a$ is called a square modulo $n$ if there exists an integer $x$ such that

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

That means $a$ is the remainder you get from squaring some integer and reducing the result modulo $n$.

Another common name for this idea is a quadratic residue modulo $n$. So, in many settings, the phrases “square modulo $n$” and “quadratic residue modulo $n$” mean the same thing.

Simple example modulo $7$

Let’s square the integers $0$ through $6$ and reduce each result modulo $7$:

$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 possible square values modulo $7$ are $0, 1, 2,$ and $4. That means these are the quadratic residues modulo $7$. The numbers $3, 5,$ and $6$ are not squares modulo $7.

This is a nice example of a pattern that is not obvious from ordinary arithmetic. Even though many numbers are possible as squares in the integers, only some remainders can appear modulo a fixed $n$.

How to find squares modulo $n$

A basic way to find all squares modulo $n$ is to compute $x^2 \bmod n$ for every residue class $x = 0, 1, 2, \dots, n-1$. This works because every integer has one of these remainders modulo $n$.

For example, modulo $8$:

$0^2 \equiv 0 \pmod 8$
$1^2 \equiv 1 \pmod 8$
$2^2 \equiv 4 \pmod 8$
$3^2 \equiv 9 \equiv 1 \pmod 8$
$4^2 \equiv 16 \equiv 0 \pmod 8$
$5^2 \equiv 25 \equiv 1 \pmod 8$
$6^2 \equiv 36 \equiv 4 \pmod 8$
$7^2 \equiv 49 \equiv 1 \pmod 8$

So the only squares modulo $8$ are $0, 1,$ and $4.

Important observation

Sometimes different numbers give the same square modulo $n$. For example, modulo $7$, both $2$ and $5$ square to $4$, because $2 \equiv -5 \pmod 7$ and squaring removes the sign:

$$(-x)^2 = x^2.$$

This means square patterns are often symmetric. If $x$ is a square root of $a$ modulo $n$, then $-x$ is also a square root of $a$ modulo $n$.

A closer look at the pattern

Squares modulo $n$ are not random. They follow rules based on the number $n$.

Example modulo a prime

When $p$ is an odd prime, not every nonzero residue modulo $p$ is a square. In fact, exactly half of the nonzero residues are quadratic residues, and the other half are not.

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

$0^2 \equiv 0$
$1^2 \equiv 1$
$2^2 \equiv 4$
$3^2 \equiv 9$
$4^2 \equiv 16 \equiv 5$
$5^2 \equiv 25 \equiv 3$
$6^2 \equiv 36 \equiv 3$
$7^2 \equiv 49 \equiv 5$
$8^2 \equiv 64 \equiv 9$
$9^2 \equiv 81 \equiv 4$
$10^2 \equiv 100 \equiv 1$

So the quadratic residues modulo $11$ are $0, 1, 3, 4, 5,$ and $9. That is six values total, and five of them are nonzero. Since there are $10$ nonzero residues modulo $11$, exactly half of them are squares.

This is a major fact in number theory and leads directly to the Legendre symbol, which is used to test whether a number is a square modulo an odd prime.

Example modulo a composite number

For composite $n$, the pattern can be more complicated. Modulo $12$, the squares are:

$0^2 \equiv 0$
$1^2 \equiv 1$
$2^2 \equiv 4$
$3^2 \equiv 9$
$4^2 \equiv 4$
$5^2 \equiv 1$
$6^2 \equiv 0$
$7^2 \equiv 1$
$8^2 \equiv 4$
$9^2 \equiv 9$
$10^2 \equiv 4$
$11^2 \equiv 1$

So the squares modulo $12$ are only $0, 1, 4,$ and $9$. That is much fewer than the $12 possible remainders.

This shows that the structure of squares depends strongly on the modulus. The arithmetic of prime moduli is especially clean, while composite moduli often require deeper tools.

How this connects to quadratic residues

The phrase quadratic residue refers to exactly this question: is a number a square modulo $n$?

If there exists an integer $x$ such that

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

then $a$ is a quadratic residue modulo $n$.

If no such $x$ exists, then $a$ is a quadratic nonresidue modulo $n$.

For odd primes $p$, the Legendre symbol is used to summarize this information:

$$\left(\frac{a}{p}\right) = \begin{cases}

1 & \text{if } a \text{ is a nonzero square modulo } p, \\

-1 & \text{if } a \text{ is a nonresidue modulo } p, \\

0 & \text{if } p \mid a.

$\end{cases}$$$

You do not need to master the Legendre symbol right away, but it is important to see how it grows out of the idea of squares modulo $n$. In other words, squares modulo $n$ are the starting point; quadratic residues are the formal language; and the Legendre symbol is a compact notation for the prime-modulus case.

Strategies for solving problems

When you are asked about squares modulo $n$, these strategies can help:

1. List small squares

For small moduli, the fastest method is often to compute $x^2 \bmod n$ for each $x$ from $0$ to $n-1$.

2. Use symmetry

Since $x^2 \equiv (-x)^2 \pmod n$, values often repeat in pairs. This can reduce work.

3. Check whether the number even has a chance

Some moduli have strong restrictions. For example, modulo $8$, no square is congruent to $2, 3, 5, 6,$ or $7$. So if someone asks whether $x^$2 \equiv 6$ \pmod 8 has a solution, you can answer no immediately.

4. Look for patterns from factors

When $n$ is composite, sometimes you can study the problem modulo factors of $n$. This idea becomes more powerful in advanced number theory.

Real-world style example

Suppose a coder wants to test whether a number can be written as a square remainder modulo $13$. The squares modulo $13$ are found by computing:

$$x^2 \bmod 13 \quad \text{for } x = 0,1,2,\dots,12.$$

The resulting square residues are $0, 1, 3, 4, 9, 10,$ and $12$. If the coder sees $8, they know it is not a square modulo $13$. This kind of idea appears in algorithms, cryptography, and error-checking systems 🔐

The key point is that modular squares let us ask a yes-or-no question: “Can this number be a square under this modulus?” That question is simple to state, but often surprisingly rich.

Conclusion

Squares modulo $n$ are the starting point for understanding quadratic residues. A number is a square modulo $n$ if it can be written as $x^2 \equiv a \pmod n$ for some integer $x$. By listing squares, spotting patterns, and comparing prime and composite moduli, you build the tools needed for deeper number theory.

This lesson connects directly to the broader quadratic residues topic and prepares you for the Legendre symbol, residue tests, and more advanced modular reasoning. If you can identify squares modulo $n$, you already understand one of the central ideas in the subject, students.

Study Notes

A number $a$ is a square modulo $n$ if there exists an integer $x$ such that $x^2 \equiv a \pmod n$.
Squares modulo $n$ are also called quadratic residues modulo $n$.
To find squares modulo $n$, compute $x^2 \bmod n$ for $x = 0,1,2,\dots,n-1$.
Different values of $x$ can give the same square modulo $n$, especially because $x^2 \equiv (-x)^2 \pmod n$.
For an odd prime $p$, exactly half of the nonzero residues modulo $p$ are squares.
For composite $n$, square patterns can be more complicated and often include fewer possible residues.
The Legendre symbol summarizes whether a number is a square modulo an odd prime.
Squares modulo $n$ are the foundation for many problems in number theory and modular arithmetic.