Skip to content

Legendre Symbol

Let $p$ be an odd prime and let $a\in\mathbb{Z}$. The Legendre symbol is defined by

number-theory book chatgpt

Definition

Let pp be an odd prime and let a∈Za\in\mathbb{Z}. The Legendre symbol is defined by

(ap)={      0if p∣a,      1if a is a quadratic residue modulo p,−1if a is a quadratic nonresidue modulo p. \left(\frac{a}{p}\right) = \begin{cases} \;\;\;0 & \text{if } p\mid a,\\ \;\;\;1 & \text{if } a \text{ is a quadratic residue modulo } p,\\ -1 & \text{if } a \text{ is a quadratic nonresidue modulo } p. \end{cases}

genui{“math_block_widget_always_prefetch_v2”:{“content”:"\left(\frac{a}{p}\right)"} }

Thus the Legendre symbol encodes whether the congruence

x2≡a(modp) x^2\equiv a\pmod p

has a solution.

For example, modulo 77, the quadratic residues are

1,2,4. 1,2,4.

Hence

(27)=1,(37)=−1,(77)=0. \left(\frac{2}{7}\right)=1, \qquad \left(\frac{3}{7}\right)=-1, \qquad \left(\frac{7}{7}\right)=0.

The Legendre symbol provides compact notation for quadratic residue questions.

Dependence on Residue Class

The value of

(ap) \left(\frac{a}{p}\right)

depends only on the residue class of aa modulo pp.

Indeed, if

a≡b(modp), a\equiv b\pmod p,

then the congruences

x2≡a(modp) x^2\equiv a\pmod p

and

x2≡b(modp) x^2\equiv b\pmod p

are equivalent. Therefore

(ap)=(bp). \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right).

For instance,

10≡3(mod7), 10\equiv3\pmod7,

so

(107)=(37)=−1. \left(\frac{10}{7}\right) = \left(\frac{3}{7}\right) =-1.

Euler’s Criterion

A fundamental characterization of the Legendre symbol is given by Euler’s criterion.

Theorem. Let pp be an odd prime and let aa be an integer with

p∤a. p\nmid a.

Then

(ap)≡a(p−1)/2(modp). \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p.

(ap)≡a(p−1)/2(modp) \left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p

Since the Legendre symbol takes only the values ±1\pm1, Euler’s criterion gives

a(p−1)/2≡1(modp) a^{(p-1)/2}\equiv1\pmod p

if aa is a quadratic residue, and

a(p−1)/2≡−1(modp) a^{(p-1)/2}\equiv-1\pmod p

otherwise.

Example

Determine whether 33 is a quadratic residue modulo 77.

Compute

3(7−1)/2=33=27≡6≡−1(mod7). 3^{(7-1)/2}=3^3=27\equiv6\equiv-1\pmod7.

Hence

(37)=−1. \left(\frac37\right)=-1.

Therefore 33 is a quadratic nonresidue modulo 77.

Multiplicativity

The Legendre symbol satisfies an important multiplicative property.

Theorem.

$$ \left(\frac{ab}{p}\right)

\left(\frac{a}{p}\right) \left(\frac{b}{p}\right). $$

This property allows complicated symbols to be decomposed into simpler ones.

Example

Compute

(611). \left(\frac{6}{11}\right).

Since

6=2⋅3, 6=2\cdot3,

we have

$$ \left(\frac{6}{11}\right)

\left(\frac{2}{11}\right) \left(\frac{3}{11}\right). $$

Now:

(211)=−1,(311)=1, \left(\frac{2}{11}\right)=-1, \qquad \left(\frac{3}{11}\right)=1,

so

(611)=−1. \left(\frac{6}{11}\right)=-1.

Hence 66 is a quadratic nonresidue modulo 1111.

The Symbols (−1p)\left(\frac{-1}{p}\right) and (2p)\left(\frac{2}{p}\right)

Two special cases occur frequently.

Residues of −1-1

The congruence

x2≡−1(modp) x^2\equiv-1\pmod p

has a solution exactly when

p≡1(mod4). p\equiv1\pmod4.

Equivalently,

$$ \left(\frac{-1}{p}\right)

(-1)^{(p-1)/2}. $$

Thus

(−15)=1,(−17)=−1. \left(\frac{-1}{5}\right)=1, \qquad \left(\frac{-1}{7}\right)=-1.

Residues of 22

The value of

(2p) \left(\frac{2}{p}\right)

depends on p(mod8)p\pmod8:

$$ \left(\frac{2}{p}\right)

(-1)^{(p^2-1)/8}. $$

Hence:

p(mod8)p \pmod 8(2p)\left(\frac{2}{p}\right)
1,71,711
3,53,5−1-1

These formulas become important ingredients in quadratic reciprocity.

Counting Solutions

The Legendre symbol also helps count solutions of quadratic congruences.

If

p∤a, p\nmid a,

then:

  • if
(ap)=1, \left(\frac{a}{p}\right)=1,

the congruence

x2≡a(modp) x^2\equiv a\pmod p

has exactly two solutions modulo pp,

  • if
(ap)=−1, \left(\frac{a}{p}\right)=-1,

it has none.

This follows because if xx is a solution, then so is −x-x, and these are distinct modulo an odd prime.

Connection with Finite Fields

The nonzero elements of the finite field

Fp \mathbb{F}_p

form a multiplicative cyclic group of order

p−1. p-1.

An element is a quadratic residue precisely when it is a square in this group.

Thus the Legendre symbol detects whether an element lies in the subgroup of squares, which has index 22.

This group-theoretic viewpoint generalizes naturally to higher residue symbols and algebraic number fields.

Toward Quadratic Reciprocity

The central question of quadratic residue theory is:

Given distinct odd primes pp and qq, when is

q q

a quadratic residue modulo pp?

The answer is provided by the quadratic reciprocity law, discovered by entity[“people”,“Carl Friedrich Gauss”,“German mathematician”].

The Legendre symbol provides the language in which quadratic reciprocity is naturally expressed.