Legendre Symbols

# Legendre Symbols

Suppose that we want to determine whether or not a quadratic congruence has solutions or not. We can determine just that utilizing what are called Legendre symbols for quadratic congruences in the form $x^2 \equiv a \pmod p$ where p is an odd prime and $p \nmid a$:

 Definition: Suppose p is an odd prime and $p \nmid a$. The Legendre symbol $(a/p)$ is defined by $(a/p) = 1$ if a is a quadratic residue (mod p) and $(a/p) = -1$ if a is a quadratic nonresidue (mod p). If p is not an odd prime, or if p divides a then the Legendre symbol is undefined.

## Example 1

Which of the following Legendre symbols are defined? A) $(9/5)$, B) $(52/13)$, C) $(19/2)$, and D) $(11/50)$.

• A) The Legendre symbol $(9/5)$ is defined since 5 is an odd prime and 5 does not divide 9.
• B) The Legendre symbol $(52/13)$ is NOT defined. 13 is an odd prime, but 13 divides 52.
• C) The Legendre symbol $(19/2)$ is NOT defined. 2 is an even prime.
• D) The Legendre symbol $(11/50)$ is NOT defined. 50 is not a prime.

# Properties of the Legendre Symbol

## Lemma 1: If a ≡ b (mod p), then the legendre symbol (a/p) = (b/p).

• Proof: This should come rather obvious. If $x^2 \equiv a \pmod p$ has solutions (or doesn't have solutions), then it follows that $x^2 \equiv b \pmod p$ should have solutions (or not) whenever $a \equiv b \pmod p$, the exact same ones.

To apply property one, suppose that we want to determine if the quadratic congruence $x^2 \equiv 5 \pmod {13}$ has solutions. This congruence is the same as $x^2 \equiv 18 \pmod {13}$. The Legendre symbol $(5/13)$ must be equal to the Legendre symbol $(18/15)$.

## Lemma 2: If p does not divide a then (a2/p) = 1.

• Proof: Property 2 implies that $x^2 \equiv a^2 \pmod p$, which obviously has solutions, more specifically, the least residue of a (mod p).

## Lemma 3: If p does not divide ab, then (ab/p) = (a/p)(b/p)

• Proof: Using Euler's Criterion, we know that $(a/p) = 1$ if $a^{(\frac{p-1}{2})} \equiv 1 \pmod p$ and that $(a/p) = -1$ if $a^{(\frac{p-1}{2})} \equiv -1 \pmod p$. Hence it follows that:
(1)
\begin{align} (a/p) \equiv a^{(\frac{p-1}{2})} \pmod p \\ (ab/p) \equiv (ab)^{(\frac{p-1}{2})} \pmod p \\ (ab/p) \equiv a^{(\frac{p-1}{2})} b^{(\frac{p-1}{2})} \pmod p \\ (ab/p) = (a/p)(b/p) \pmod p \end{align}
• Note that the left hand side of the congruence is either 1 or -1, and the right hand side of the congruence is the same. The only way that $(ab/p) \equiv (a/p)(b/p) \pmod p$ is when $(ab/p) = (a/p)(b/p)$ since p is restricted to being an odd prime.

# Other Properties of Legendre Symbols

There are many other rules that have been established regarding Legendre symbols, some of which are often necessary to evaluate Legendre symbols. We will state a few of them on this page and subsequently prove them all in future pages:

(2)
\begin{align} (-1/p) = \begin{Bmatrix} 1 & p \equiv 1 \pmod {4} \\ -1 & p \equiv 3 \pmod {4}\\ \end{Bmatrix} \end{align}
(3)
\begin{align} (2/p) = \begin{Bmatrix} 1 & p \equiv 1 \pmod {8} \quad \mathbf{or} \quad p \equiv 7 \pmod {8}\\ -1 & p \equiv 3 \pmod {8} \quad \mathbf{or} \quad p \equiv 5 \pmod {8}\\ \end{Bmatrix} \end{align}
(4)
\begin{align} (3/p) = \begin{Bmatrix} 1 & \mathbf{if} \quad p \equiv 1 \pmod {12} \quad \mathbf{or} \quad p \equiv 11 \pmod {12}\\ -1 & \mathbf{if} \quad p \equiv 5 \pmod {12} \quad \mathbf{or} \quad p \equiv 7 \pmod {12}\\ \end{Bmatrix} \end{align}
(5)
\begin{align} (6/p) = \begin{Bmatrix} 1 & \mathbf{if} \quad p \equiv 1, 5, 19, \: \mathbf{or} \: 23 \pmod {24} \\ -1 & \mathbf{if} \quad p \equiv 7, 11, 13, \: \mathbf{or} \: 17 \pmod {24} \end{Bmatrix} \end{align}