Number Theory • Topic 25

Legendre Symbol

The Legendre Symbol is a concise notation used to determine if an integer is a quadratic residue modulo an odd prime $p$ . It transforms questions about quadratic equations into arithmetic calculations.

Definition

Definition (Legendre Symbol)

For an integer

a

and an odd prime

p

, the Legendre Symbol

(\frac{a}{p})

is defined as:

$1$ : if $a$ is a quadratic residue modulo $p$ and $a \neq \equiv 0 (mod p)$ .
$- 1$ : if $a$ is a quadratic non-residue modulo $p$ .
$0$ : if $p ∣ a$ .

Key Properties

1. Multiplicativity

The Legendre symbol is completely multiplicative:

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

This means the product of two residues is a residue ( $1 \cdot 1 = 1$ ).
The product of two non-residues is a residue ( $(- 1) \cdot (- 1) = 1$ ).
The product of a residue and a non-residue is a non-residue ( $1 \cdot (- 1) = - 1$ ).

2. Periodicity

a \equiv b (mod p)

, then:

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

3. The Square Factor

(\frac{a ^{2}}{p}) = 1 (if p ∤ a)

(\frac{a ^{2} b}{p}) = (\frac{b}{p})

Practice Problems

Exercise (Problem 1)

Compute

(\frac{50}{7})

using multiplicativity and periodicity.

Exercise (Problem 2)

Evaluate

(\frac{- 1}{p})

for

p = 17

and

p = 19

Exercise (Problem 3)

Prove that

\sum_{a = 1}^{p - 1} (\frac{a}{p}) = 0

. (Hint: There are equal numbers of residues and non-residues).