# 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^{2}/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:

- 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):

- For the Legendre symbol (2/p):

- For the Legendre symbol (3/p):

- For the Legendre symbol (6/p):

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