Quadratic residues: why exactly half the nonzero elements mod p are squares

The squaring map x -> x^2 is 2-to-1, which forces exactly (p-1)/2 quadratic residues. We develop the Legendre symbol, Euler's criterion, the law of quadratic reciprocity, and the Tonelli-Shanks algorithm for extracting square roots modulo a prime.

Folio Official

March 1, 2026

Modulo $7$ , the squares of the nonzero elements are $1^{2} = 1$ , $2^{2} = 4$ , $3^{2} = 2$ , $4^{2} = 2$ , $5^{2} = 4$ , $6^{2} = 1$ . The set of values is ${1, 2, 4}$ – exactly half of ${1, 2, 3, 4, 5, 6}$ . This is no coincidence. In this article we explain why, modulo any odd prime, precisely half of the nonzero residues are squares, and we develop the theory that grows from this observation.

1 Definition of quadratic residues

Definition 1 (Quadratic residue).

Let

p

be an odd prime and

g cd (a, p) = 1

. If there exists

x

such that

x^{2} \equiv a (mod p)

, then

a

is a quadratic residue modulo

p

. Otherwise,

a

is a quadratic non-residue.

Example 2.

For

p = 7

, squaring each element of

{1, 2, \dots, 6}

modulo

7

1^{2} \equiv 1, 2^{2} \equiv 4, 3^{2} \equiv 2, 4^{2} \equiv 2, 5^{2} \equiv 4, 6^{2} \equiv 1.

The quadratic residues are

{1, 2, 4}

; the non-residues are

{3, 5, 6}

2 Why exactly half: the squaring map is 2-to-1

Theorem 3.

Let

p

be an odd prime. Among

1, 2, \dots, p - 1

, exactly

(p - 1) /2

are quadratic residues and exactly

(p - 1) /2

are quadratic non-residues.

Proof.

Define

f : (Z / p Z)^{*} \to (Z / p Z)^{*}

f (x) = x^{2}

. Since

x^{2} \equiv (- x)^{2} (mod p)

, each

x

and

p - x

(

\equiv - x

) map to the same value. Moreover

x \neq = p - x

because

p

is odd (so

2 x \neq \equiv 0 (mod p)

Conversely, if

x^{2} \equiv y^{2} (mod p)

, then

p ∣ (x - y) (x + y)

. By Euclid's lemma, either

x \equiv y

x \equiv - y (mod p)

Thus each quadratic residue is the image of exactly

2

elements. The number of distinct images is

(p - 1) /2

. □

Remark 4.

Intuitively, pair up

{1, 2, \dots, p - 1}

into

(p - 1) /2

pairs

{x, - x}

. Each pair produces one quadratic residue. So there are exactly

(p - 1) /2

of them.

3 The Legendre symbol

Definition 5 (Legendre symbol).

For an odd prime

p

and

g cd (a, p) = 1

(\frac{a}{p}) = {1 - 1 if a is a quadratic residue mod p, if a is a quadratic non-residue mod p .

When

p ∣ a

, we set

(\frac{a}{p}) = 0

Remark 6.

The Legendre symbol is completely multiplicative:

(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})

. This encodes the rules "residue

\times

residue = residue," "residue

\times

non-residue = non-residue," and "non-residue

\times

non-residue = residue" – precisely the multiplication table of

{1, - 1}

4 Euler's criterion: an efficient test

Theorem 7 (Euler's criterion).

For an odd prime

p

with

g cd (a, p) = 1

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p) .

Proof.

a

is a quadratic residue, write

a \equiv x^{2}

. Then

a^{(p - 1) /2} \equiv x^{p - 1} \equiv 1 (mod p)

by Fermat's little theorem.

a

is a non-residue: the polynomial

x^{p - 1} - 1 \equiv 0 (mod p)

has at most

p - 1

roots. Factor it as

x^{p - 1} - 1 = (x^{(p - 1) /2} - 1) (x^{(p - 1) /2} + 1)

. The

(p - 1) /2

quadratic residues supply

(p - 1) /2

roots of

x^{(p - 1) /2} - 1

, exhausting all its roots. The remaining

(p - 1) /2

elements (the non-residues) must satisfy

x^{(p - 1) /2} \equiv - 1

. □

Remark 8.

Euler's criterion allows us to determine whether

a

is a quadratic residue in

O (lo g p)

time via repeated squaring, without factoring

a

5 The law of quadratic reciprocity: the most surprising theorem

Theorem 9 (Quadratic reciprocity (Gauss)).

For distinct odd primes

p

and

q

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} .

Remark 10 (Why this is surprising).

(\frac{p}{q})

asks whether

p

is a square modulo

q

(\frac{q}{p})

asks whether

q

is a square modulo

p

. These are questions about two entirely different worlds– arithmetic modulo

q

and arithmetic modulo

p

– yet the law of quadratic reciprocity links them. The sign flips precisely when

p \equiv q \equiv 3 (mod 4)

; otherwise the two symbols agree.

Gauss called this the "golden theorem" (theorema aureum) and gave eight different proofs over his lifetime.

Example 11.

23

a quadratic residue modulo

59

? Rather than computing directly, apply reciprocity:

(\frac{23}{59}) (\frac{59}{23}) = (- 1)^{11 \times 29} = (- 1)^{319} = - 1.

Since

59 \equiv 13 (mod 23)

, we have

(\frac{59}{23}) = (\frac{13}{23})

. The law can be applied repeatedly to reduce the problem to trivial cases.

6 The Tonelli–Shanks algorithm

Once we know that $a$ is a quadratic residue modulo $p$ , we may want to find an actual square root.

Remark 12 (Tonelli–Shanks).

The Tonelli–Shanks algorithm computes a solution

x

x^{2} \equiv a (mod p)

. Write

p - 1 = 2^{s} q

with

q

odd, find a quadratic non-residue

n

, and iteratively construct the square root. The running time is

O (lo g^{2} p)

In the special case

p \equiv 3 (mod 4)

, the answer is simply

x \equiv a^{(p + 1) /4} (mod p)

, since

x^{2} \equiv a^{(p + 1) /2} = a \cdot a^{(p - 1) /2} \equiv a \cdot 1 = a

7 Takeaway

Exactly $(p - 1) /2$ of the nonzero residues modulo $p$ are quadratic residues (because $x \mapsto x^{2}$ is a 2-to-1 map).
The Legendre symbol encodes quadratic residuosity as $\pm 1$ and is completely multiplicative.
Euler's criterion provides an $O (lo g p)$ test.
The law of quadratic reciprocity is a remarkable link between the arithmetic of two different primes.
The Tonelli–Shanks algorithm efficiently extracts square roots modulo $p$ .

In the next article, we discover another face of the Euclidean algorithm – continued fractions and the theory of best rational approximations.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Quadratic residues: why exactly half the nonzero elements mod p are squares

Folio Official

March 1, 2026

1 Definition of quadratic residues

Definition 1 (Quadratic residue).

Let

p

be an odd prime and

g cd (a, p) = 1

. If there exists

x

such that

x^{2} \equiv a (mod p)

, then

a

is a quadratic residue modulo

p

. Otherwise,

a

is a quadratic non-residue.

Example 2.

For

p = 7

, squaring each element of

{1, 2, \dots, 6}

modulo

7

1^{2} \equiv 1, 2^{2} \equiv 4, 3^{2} \equiv 2, 4^{2} \equiv 2, 5^{2} \equiv 4, 6^{2} \equiv 1.

The quadratic residues are

{1, 2, 4}

; the non-residues are

{3, 5, 6}

2 Why exactly half: the squaring map is 2-to-1

Theorem 3.

Let

p

be an odd prime. Among

1, 2, \dots, p - 1

, exactly

(p - 1) /2

are quadratic residues and exactly

(p - 1) /2

are quadratic non-residues.

Proof.

Define

f : (Z / p Z)^{*} \to (Z / p Z)^{*}

f (x) = x^{2}

. Since

x^{2} \equiv (- x)^{2} (mod p)

, each

x

and

p - x

(

\equiv - x

) map to the same value. Moreover

x \neq = p - x

because

p

is odd (so

2 x \neq \equiv 0 (mod p)

Conversely, if

x^{2} \equiv y^{2} (mod p)

, then

p ∣ (x - y) (x + y)

. By Euclid's lemma, either

x \equiv y

x \equiv - y (mod p)

Thus each quadratic residue is the image of exactly

2

elements. The number of distinct images is

(p - 1) /2

. □

Remark 4.

Intuitively, pair up

{1, 2, \dots, p - 1}

into

(p - 1) /2

pairs

{x, - x}

. Each pair produces one quadratic residue. So there are exactly

(p - 1) /2

of them.

3 The Legendre symbol

Definition 5 (Legendre symbol).

For an odd prime

p

and

g cd (a, p) = 1

(\frac{a}{p}) = {1 - 1 if a is a quadratic residue mod p, if a is a quadratic non-residue mod p .

When

p ∣ a

, we set

(\frac{a}{p}) = 0

Remark 6.

The Legendre symbol is completely multiplicative:

(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p})

. This encodes the rules "residue

\times

residue = residue," "residue

\times

non-residue = non-residue," and "non-residue

\times

non-residue = residue" – precisely the multiplication table of

{1, - 1}

4 Euler's criterion: an efficient test

Theorem 7 (Euler's criterion).

For an odd prime

p

with

g cd (a, p) = 1

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p) .

Proof.

a

is a quadratic residue, write

a \equiv x^{2}

. Then

a^{(p - 1) /2} \equiv x^{p - 1} \equiv 1 (mod p)

by Fermat's little theorem.

a

is a non-residue: the polynomial

x^{p - 1} - 1 \equiv 0 (mod p)

has at most

p - 1

roots. Factor it as

x^{p - 1} - 1 = (x^{(p - 1) /2} - 1) (x^{(p - 1) /2} + 1)

. The

(p - 1) /2

quadratic residues supply

(p - 1) /2

roots of

x^{(p - 1) /2} - 1

, exhausting all its roots. The remaining

(p - 1) /2

elements (the non-residues) must satisfy

x^{(p - 1) /2} \equiv - 1

. □

Remark 8.

Euler's criterion allows us to determine whether

a

is a quadratic residue in

O (lo g p)

time via repeated squaring, without factoring

a

5 The law of quadratic reciprocity: the most surprising theorem

Theorem 9 (Quadratic reciprocity (Gauss)).

For distinct odd primes

p

and

q

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} .

Remark 10 (Why this is surprising).

(\frac{p}{q})

asks whether

p

is a square modulo

q

(\frac{q}{p})

asks whether

q

is a square modulo

p

. These are questions about two entirely different worlds– arithmetic modulo

q

and arithmetic modulo

p

– yet the law of quadratic reciprocity links them. The sign flips precisely when

p \equiv q \equiv 3 (mod 4)

; otherwise the two symbols agree.

Gauss called this the "golden theorem" (theorema aureum) and gave eight different proofs over his lifetime.

Example 11.

23

a quadratic residue modulo

59

? Rather than computing directly, apply reciprocity:

(\frac{23}{59}) (\frac{59}{23}) = (- 1)^{11 \times 29} = (- 1)^{319} = - 1.

Since

59 \equiv 13 (mod 23)

, we have

(\frac{59}{23}) = (\frac{13}{23})

. The law can be applied repeatedly to reduce the problem to trivial cases.

6 The Tonelli–Shanks algorithm

Once we know that $a$ is a quadratic residue modulo $p$ , we may want to find an actual square root.

Remark 12 (Tonelli–Shanks).

The Tonelli–Shanks algorithm computes a solution

x

x^{2} \equiv a (mod p)

. Write

p - 1 = 2^{s} q

with

q

odd, find a quadratic non-residue

n

, and iteratively construct the square root. The running time is

O (lo g^{2} p)

In the special case

p \equiv 3 (mod 4)

, the answer is simply

x \equiv a^{(p + 1) /4} (mod p)

, since

x^{2} \equiv a^{(p + 1) /2} = a \cdot a^{(p - 1) /2} \equiv a \cdot 1 = a

7 Takeaway

Exactly $(p - 1) /2$ of the nonzero residues modulo $p$ are quadratic residues (because $x \mapsto x^{2}$ is a 2-to-1 map).
The Legendre symbol encodes quadratic residuosity as $\pm 1$ and is completely multiplicative.
Euler's criterion provides an $O (lo g p)$ test.
The law of quadratic reciprocity is a remarkable link between the arithmetic of two different primes.
The Tonelli–Shanks algorithm efficiently extracts square roots modulo $p$ .

In the next article, we discover another face of the Euclidean algorithm – continued fractions and the theory of best rational approximations.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Quadratic residues: why exactly half the nonzero elements mod p are squares

1 Definition of quadratic residues

2 Why exactly half: the squaring map is 2-to-1

3 The Legendre symbol

4 Euler's criterion: an efficient test

5 The law of quadratic reciprocity: the most surprising theorem

6 The Tonelli–Shanks algorithm

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Quadratic residues: why exactly half the nonzero elements mod p are squares

1 Definition of quadratic residues

2 Why exactly half: the squaring map is 2-to-1

3 The Legendre symbol

4 Euler's criterion: an efficient test

5 The law of quadratic reciprocity: the most surprising theorem

6 The Tonelli–Shanks algorithm

7 Takeaway

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division