Quadratic Residues and the Law of Reciprocity — The Theory of Quadratic Residues

We define the Legendre symbol, prove Euler's criterion, and establish Gauss's lemma. We then prove the law of quadratic reciprocity and discuss the Jacobi symbol and the Tonelli--Shanks algorithm for computing square roots modulo primes.

Folio Official

March 1, 2026

1 Quadratic Residues

Definition 1 (Quadratic residue).

Let

p

be an odd prime and

a

an integer with

p ∤ a

. If the congruence

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

has a solution, then

a

is called a quadratic residue modulo

p

. Otherwise,

a

is a quadratic non-residue modulo

p

Definition 2 (Legendre symbol).

For an odd prime

p

and an integer

a

, the Legendre symbol is defined by

(\frac{a}{p}) = ⎩ ⎨ ⎧ 01 - 1 if p ∣ a, if a is a quadratic residue mod p, if a is a quadratic non-residue mod p .

Theorem 3.

Among

1, 2, \dots, p - 1

, exactly

(p - 1) /2

are quadratic residues modulo

p

and exactly

(p - 1) /2

are quadratic non-residues.

Proof.

Define

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

f (\overset{x}{ˉ}) = \overset{x}{ˉ}^{2}

. We have

f (\overset{x}{ˉ}) = f (\overset{y}{ˉ})

if and only if

\overset{x}{ˉ}^{2} = \overset{y}{ˉ}^{2}

, equivalently

\overset{x}{ˉ} = \pm \overset{y}{ˉ}

. Thus each quadratic residue is the image of exactly two elements, so the number of quadratic residues is

(p - 1) /2

. □

2 Euler's Criterion

Theorem 4 (Euler's criterion).

For an odd prime

p

and an integer

a

with

p ∤ a

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

Proof.

a

is a quadratic residue, say

a \equiv x^{2}

, then

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

by Fermat's little theorem. The polynomial

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

has degree

(p - 1) /2

over

(Z / p Z)^{*}

and therefore at most

(p - 1) /2

roots; the

(p - 1) /2

quadratic residues account for all of them. Hence

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

if and only if

a

is a quadratic residue. Since

a^{p - 1} \equiv 1

, we have

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

, so

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

. For a quadratic non-residue, we conclude

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

. □

3 Gauss's Lemma

Lemma 5 (Gauss's lemma).

Let

p

be an odd prime and

p ∤ a

. Among the residues of

a, 2 a, 3 a, \dots, \frac{p - 1}{2} a

reduced to representatives in

{- (p - 1) /2, \dots, - 1, 1, \dots, (p - 1) /2}

, let

μ

denote the number of negative representatives. Then

(\frac{a}{p}) = (- 1)^{μ} .

Proof.

Let

s_{1}, s_{2}, \dots, s_{(p - 1) /2}

be the reduced representatives. Their absolute values

∣ s_{1} ∣, ∣ s_{2} ∣, \dots, ∣ s_{(p - 1) /2} ∣

form a permutation of

{1, 2, \dots, (p - 1) /2}

. (If

∣ s_{i} ∣ = ∣ s_{j} ∣

with

i \neq = j

, then

ia \equiv \pm ja (mod p)

, giving

i = j

i + j \equiv 0

; the latter is impossible since

1 \leq i, j \leq (p - 1) /2

.) Hence

\prod s_{i} = (- 1)^{μ} \cdot ((p - 1) /2)!

, while

\prod s_{i} \equiv \prod_{i = 1}^{(p - 1) /2} ia = ((p - 1) /2)! \cdot a^{(p - 1) /2}

. Dividing both sides by

((p - 1) /2)!

yields

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

. The result now follows from Euler's criterion. □

4 The First Supplement to Quadratic Reciprocity

Theorem 6 (First supplement).

For an odd prime

p

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2} = {1 - 1 if p \equiv 1 (mod 4), if p \equiv 3 (mod 4) .

In other words,

- 1

is a quadratic residue modulo

p

if and only if

p \equiv 1 (mod 4)

Proof.

By Euler's criterion,

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

. Since

(- 1)^{(p - 1) /2} = \pm 1

and

p \geq 3

(so

1 \neq \equiv - 1 (mod p)

), the congruence holds as an equality of integers. When

p \equiv 1 (mod 4)

, the exponent

(p - 1) /2

is even, giving

(\frac{- 1}{p}) = 1

. When

p \equiv 3 (mod 4)

, the exponent is odd, giving

(\frac{- 1}{p}) = - 1

. □

5 The Law of Quadratic Reciprocity

Theorem 7 (Quadratic reciprocity).

For distinct odd primes

p, q

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

Proof.

Using Gauss's lemma, we write

(\frac{q}{p}) = (- 1)^{μ}

and reduce the count

μ

to a lattice-point enumeration. Consider the rectangle

R = {(x, y) ∣ 1 \leq x \leq (p - 1) /2, 1 \leq y \leq (q - 1) /2}

. The number

μ

of negative representatives of

q x mod p

equals the number of lattice points below the line

y = q x / p

that lie in a certain complementary region. A symmetric argument applies to

μ^{'}

, where

(\frac{p}{q}) = (- 1)^{μ^{'}}

. Combining yields

μ + μ^{'} = (p - 1) (q - 1) /4

, and therefore

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{(p - 1) (q - 1) /4}

. □

6 The Jacobi Symbol

Definition 8 (Jacobi symbol).

For an odd positive integer

n = p_{1} p_{2} \dots p_{k}

(where the

p_{i}

are odd primes, not necessarily distinct), the Jacobi symbol is defined as

(\frac{a}{n}) = \prod_{i = 1}^{k} (\frac{a}{p _{i}})

Remark 9.

The Jacobi symbol inherits the reciprocity law and can be computed efficiently in

O (lo g^{2} n)

time without factoring

n

. One must note, however, that

(\frac{a}{n}) = 1

does not in general imply that

a

is a quadratic residue modulo

n

7 The Tonelli–Shanks Algorithm

Remark 10.

When

a

is a quadratic residue modulo a prime

p

, the Tonelli–Shanks algorithm finds a solution to

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

. It factors

p - 1 = 2^{s} q

with

q

odd, selects a quadratic non-residue

z

, and iteratively constructs the solution. The running time is

O (lo g^{2} p)

Number Theory Algebra Textbook Quadratic Residues Reciprocity

Folio Official

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

1 followers·107 articles

Quadratic Residues and the Law of Reciprocity — The Theory of Quadratic Residues

Folio Official

March 1, 2026

1 Quadratic Residues

Definition 1 (Quadratic residue).

Let

p

be an odd prime and

a

an integer with

p ∤ a

. If the congruence

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

has a solution, then

a

is called a quadratic residue modulo

p

. Otherwise,

a

is a quadratic non-residue modulo

p

Definition 2 (Legendre symbol).

For an odd prime

p

and an integer

a

, the Legendre symbol is defined by

(\frac{a}{p}) = ⎩ ⎨ ⎧ 01 - 1 if p ∣ a, if a is a quadratic residue mod p, if a is a quadratic non-residue mod p .

Theorem 3.

Among

1, 2, \dots, p - 1

, exactly

(p - 1) /2

are quadratic residues modulo

p

and exactly

(p - 1) /2

are quadratic non-residues.

Proof.

Define

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

f (\overset{x}{ˉ}) = \overset{x}{ˉ}^{2}

. We have

f (\overset{x}{ˉ}) = f (\overset{y}{ˉ})

if and only if

\overset{x}{ˉ}^{2} = \overset{y}{ˉ}^{2}

, equivalently

\overset{x}{ˉ} = \pm \overset{y}{ˉ}

. Thus each quadratic residue is the image of exactly two elements, so the number of quadratic residues is

(p - 1) /2

. □

2 Euler's Criterion

Theorem 4 (Euler's criterion).

For an odd prime

p

and an integer

a

with

p ∤ a

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

Proof.

a

is a quadratic residue, say

a \equiv x^{2}

, then

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

by Fermat's little theorem. The polynomial

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

has degree

(p - 1) /2

over

(Z / p Z)^{*}

and therefore at most

(p - 1) /2

roots; the

(p - 1) /2

quadratic residues account for all of them. Hence

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

if and only if

a

is a quadratic residue. Since

a^{p - 1} \equiv 1

, we have

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

, so

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

. For a quadratic non-residue, we conclude

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

. □

3 Gauss's Lemma

Lemma 5 (Gauss's lemma).

Let

p

be an odd prime and

p ∤ a

. Among the residues of

a, 2 a, 3 a, \dots, \frac{p - 1}{2} a

reduced to representatives in

{- (p - 1) /2, \dots, - 1, 1, \dots, (p - 1) /2}

, let

μ

denote the number of negative representatives. Then

(\frac{a}{p}) = (- 1)^{μ} .

Proof.

Let

s_{1}, s_{2}, \dots, s_{(p - 1) /2}

be the reduced representatives. Their absolute values

∣ s_{1} ∣, ∣ s_{2} ∣, \dots, ∣ s_{(p - 1) /2} ∣

form a permutation of

{1, 2, \dots, (p - 1) /2}

. (If

∣ s_{i} ∣ = ∣ s_{j} ∣

with

i \neq = j

, then

ia \equiv \pm ja (mod p)

, giving

i = j

i + j \equiv 0

; the latter is impossible since

1 \leq i, j \leq (p - 1) /2

.) Hence

\prod s_{i} = (- 1)^{μ} \cdot ((p - 1) /2)!

, while

\prod s_{i} \equiv \prod_{i = 1}^{(p - 1) /2} ia = ((p - 1) /2)! \cdot a^{(p - 1) /2}

. Dividing both sides by

((p - 1) /2)!

yields

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

. The result now follows from Euler's criterion. □

4 The First Supplement to Quadratic Reciprocity

Theorem 6 (First supplement).

For an odd prime

p

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2} = {1 - 1 if p \equiv 1 (mod 4), if p \equiv 3 (mod 4) .

In other words,

- 1

is a quadratic residue modulo

p

if and only if

p \equiv 1 (mod 4)

Proof.

By Euler's criterion,

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

. Since

(- 1)^{(p - 1) /2} = \pm 1

and

p \geq 3

(so

1 \neq \equiv - 1 (mod p)

), the congruence holds as an equality of integers. When

p \equiv 1 (mod 4)

, the exponent

(p - 1) /2

is even, giving

(\frac{- 1}{p}) = 1

. When

p \equiv 3 (mod 4)

, the exponent is odd, giving

(\frac{- 1}{p}) = - 1

. □

5 The Law of Quadratic Reciprocity

Theorem 7 (Quadratic reciprocity).

For distinct odd primes

p, q

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

Proof.

Using Gauss's lemma, we write

(\frac{q}{p}) = (- 1)^{μ}

and reduce the count

μ

to a lattice-point enumeration. Consider the rectangle

R = {(x, y) ∣ 1 \leq x \leq (p - 1) /2, 1 \leq y \leq (q - 1) /2}

. The number

μ

of negative representatives of

q x mod p

equals the number of lattice points below the line

y = q x / p

that lie in a certain complementary region. A symmetric argument applies to

μ^{'}

, where

(\frac{p}{q}) = (- 1)^{μ^{'}}

. Combining yields

μ + μ^{'} = (p - 1) (q - 1) /4

, and therefore

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{(p - 1) (q - 1) /4}

. □

6 The Jacobi Symbol

Definition 8 (Jacobi symbol).

For an odd positive integer

n = p_{1} p_{2} \dots p_{k}

(where the

p_{i}

are odd primes, not necessarily distinct), the Jacobi symbol is defined as

(\frac{a}{n}) = \prod_{i = 1}^{k} (\frac{a}{p _{i}})

Remark 9.

The Jacobi symbol inherits the reciprocity law and can be computed efficiently in

O (lo g^{2} n)

time without factoring

n

. One must note, however, that

(\frac{a}{n}) = 1

does not in general imply that

a

is a quadratic residue modulo

n

7 The Tonelli–Shanks Algorithm

Remark 10.

When

a

is a quadratic residue modulo a prime

p

, the Tonelli–Shanks algorithm finds a solution to

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

. It factors

p - 1 = 2^{s} q

with

q

odd, selects a quadratic non-residue

z

, and iteratively constructs the solution. The running time is

O (lo g^{2} p)

Number Theory Algebra Textbook Quadratic Residues Reciprocity

Folio Official

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

1 followers·107 articles

Quadratic Residues and the Law of Reciprocity — The Theory of Quadratic Residues

1 Quadratic Residues

2 Euler's Criterion

3 Gauss's Lemma

4 The First Supplement to Quadratic Reciprocity

5 The Law of Quadratic Reciprocity

6 The Jacobi Symbol

7 The Tonelli–Shanks Algorithm

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem

Quadratic Residues and the Law of Reciprocity — The Theory of Quadratic Residues

1 Quadratic Residues

2 Euler's Criterion

3 Gauss's Lemma

4 The First Supplement to Quadratic Reciprocity

5 The Law of Quadratic Reciprocity

6 The Jacobi Symbol

7 The Tonelli–Shanks Algorithm

Share your expertise with the world

More from Folio Official

Introduction to Algebraic Integers — Extending the Notion of Integer

Arithmetic Functions and Multiplicative Functions — Functions on the Integers

Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers

Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem