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.