# Squares Modulo $n$

## Quadratic Congruences

A quadratic congruence is a congruence involving a square. The basic form is

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

where $a,n\in\mathbb{Z}$ and $n>1$.

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

The problem is to determine whether there exists an integer $x$ satisfying the congruence. If such an $x$ exists, then $a$ is called a quadratic residue modulo $n$. Otherwise, $a$ is called a quadratic nonresidue modulo $n$.

Quadratic congruences form the foundation of the theory of quadratic residues, one of the central subjects of classical number theory.

## First Examples

Consider arithmetic modulo $7$. Computing the squares gives

$$
0^2\equiv0,
$$

$$
1^2\equiv1,
$$

$$
2^2\equiv4,
$$

$$
3^2\equiv9\equiv2,
$$

$$
4^2\equiv16\equiv2,
$$

$$
5^2\equiv25\equiv4,
$$

$$
6^2\equiv36\equiv1\pmod7.
$$

Thus the quadratic residues modulo $7$ are

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

The quadratic nonresidues are

$$
3,5,6.
$$

Hence the congruence

$$
x^2\equiv2\pmod7
$$

has solutions, while

$$
x^2\equiv3\pmod7
$$

does not.

## Symmetry of Squares

Modulo a prime $p$, the numbers $x$ and $-x$ always produce the same square:

$$
x^2\equiv(-x)^2\pmod p.
$$

Thus nonzero quadratic residues typically occur in pairs.

For example, modulo $11$,

$$
2^2\equiv9^2\equiv4\pmod{11}.
$$

This symmetry explains why there are only about half as many nonzero quadratic residues as nonzero residue classes.

## Number of Quadratic Residues

Let $p$ be an odd prime. Among the nonzero residue classes modulo $p$, exactly half are quadratic residues.

Indeed, the nonzero residues are

$$
1,2,\dots,p-1.
$$

Since

$$
x^2\equiv(-x)^2\pmod p,
$$

the values

$$
1^2,2^2,\dots,\left(\frac{p-1}{2}\right)^2
$$

produce all distinct nonzero quadratic residues.

Therefore there are exactly

$$
\frac{p-1}{2}
$$

nonzero quadratic residues modulo $p$.

## Solving Quadratic Congruences

To solve

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

one may test residue classes directly when $n$ is small.

For example, solve

$$
x^2\equiv4\pmod9.
$$

Checking squares modulo $9$:

$$
0^2\equiv0,
$$

$$
1^2\equiv1,
$$

$$
2^2\equiv4,
$$

$$
3^2\equiv0,
$$

$$
4^2\equiv7,
$$

$$
5^2\equiv7,
$$

$$
6^2\equiv0,
$$

$$
7^2\equiv4,
$$

$$
8^2\equiv1.
$$

Thus the solutions are

$$
x\equiv2,7\pmod9.
$$

For large moduli, more sophisticated methods are required.

## Squares Modulo Powers of Primes

Quadratic congruences modulo powers of primes are subtler.

For example,

$$
x^2\equiv1\pmod8
$$

has four solutions:

$$
x\equiv1,3,5,7\pmod8.
$$

Indeed, every odd square is congruent to $1\pmod8$.

This differs from the prime modulus case, where quadratic congruences generally have at most two solutions.

Such phenomena motivate deeper investigations into congruences modulo composite numbers.

## Polynomial Perspective

The congruence

$$
x^2\equiv a\pmod p
$$

may be viewed as the polynomial equation

$$
x^2-a=0
$$

over the finite field

$$
\mathbb{F}_p.
$$

This viewpoint connects quadratic residues with algebraic structures over finite fields.

For example, if $a$ is a quadratic residue modulo $p$, then the polynomial

$$
x^2-a
$$

factors over $\mathbb{F}_p$. Otherwise it remains irreducible.

Thus quadratic congruences link arithmetic with algebra.

## Geometric Interpretation

The congruence

$$
x^2+y^2\equiv1\pmod p
$$

defines a discrete analogue of the unit circle over the finite field $\mathbb{F}_p$.

Studying such equations leads naturally to arithmetic geometry over finite fields, a subject central to modern algebraic number theory and cryptography.

## Historical Context

The systematic study of quadratic residues began with entity["people","Leonhard Euler","Swiss mathematician"] and reached a major milestone in the work of entity["people","Carl Friedrich Gauss","German mathematician"].

Gauss regarded quadratic reciprocity as the “fundamental theorem” of arithmetic modulo primes. His investigations transformed congruence theory into a coherent mathematical discipline and laid the foundations for modern algebraic number theory.