Definition

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

$$ \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

$$ x^2\equiv a\pmod p $$

has a solution.

For example, modulo $7$, the quadratic residues are

$$ 1,2,4. $$

Hence

$$ \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

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

depends only on the residue class of $a$ modulo $p$.

Indeed, if

$$ a\equiv b\pmod p, $$

then the congruences

$$ x^2\equiv a\pmod p $$

and

$$ x^2\equiv b\pmod p $$

are equivalent. Therefore

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

For instance,

$$ 10\equiv3\pmod7, $$

so

$$ \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 $p$ be an odd prime and let $a$ be an integer with

$$ p\nmid a. $$

Then

$$ \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p. $$

$$ \left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p $$

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

$$ a^{(p-1)/2}\equiv1\pmod p $$

if $a$ is a quadratic residue, and

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

otherwise.

Example

Determine whether $3$ is a quadratic residue modulo $7$.

Compute

$$ 3^{(7-1)/2}=3^3=27\equiv6\equiv-1\pmod7. $$

Hence

$$ \left(\frac37\right)=-1. $$

Therefore $3$ is a quadratic nonresidue modulo $7$.

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

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

Since

$$ 6=2\cdot3, $$

we have

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

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

Now:

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

so

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

Hence $6$ is a quadratic nonresidue modulo $11$.

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

Two special cases occur frequently.

Residues of $-1$

The congruence

$$ x^2\equiv-1\pmod p $$

has a solution exactly when

$$ p\equiv1\pmod4. $$

Equivalently,

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

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

Thus

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

Residues of $2$

The value of

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

depends on $p\pmod8$:

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

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

Hence:

$p \pmod 8$	$\left(\frac{2}{p}\right)$
$1,7$	$1$
$3,5$	$-1$

These formulas become important ingredients in quadratic reciprocity.

Counting Solutions

The Legendre symbol also helps count solutions of quadratic congruences.

If

$$ p\nmid a, $$

then:

• if

$$ \left(\frac{a}{p}\right)=1, $$

the congruence

$$ x^2\equiv a\pmod p $$

has exactly two solutions modulo $p$,

• if

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

it has none.

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

Connection with Finite Fields

The nonzero elements of the finite field

$$ \mathbb{F}_p $$

form a multiplicative cyclic group of order

$$ 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 $2$.

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 $p$ and $q$, when is

$$ q $$

a quadratic residue modulo $p$?

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.