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 (a²/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:

• For the Legendre symbol (-1/p):

(2)

\begin{align} (-1/p) = \begin{Bmatrix} 1 & p \equiv 1 \pmod {4} \\ -1 & p \equiv 3 \pmod {4}\\ \end{Bmatrix} \end{align}

• For the Legendre symbol (2/p):

(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}

• For the Legendre symbol (3/p):

(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}

• For the Legendre symbol (6/p):

(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}

• The Quadratic Reciprocity Theorem states that $(p/q) = -(q/p)$ if $p \equiv q \equiv 3 \pmod {4}$ and $(p/q) = (q/p)$ otherwise.