Squares Modulo $n$
A quadratic congruence is a congruence involving a square. The basic form is
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.