# Legendre Symbol

## 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.