Legendre Symbol Rules for (-1/p) and (2/p)

# Legendre Symbol Rules for (-1/p) and (2/p)

We will now prove the important Legendre symbol properties for (-1/p) and (2/p) in theorems 1 and 2 such that:

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

(2)
\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}

## Theorem 1: If p is an odd prime, then (-1/p) = 1 if p ≡ 1 (mod 4), and (-1/p) = -1 if p ≡ 3 (mod 4).

**Proof:**Using Euler's Criterion, we know that $(-1/p) \equiv (-1)^{(\frac{p-1}{2})} \pmod p$. Suppose that $p \equiv 1 \pmod 4$. That is p = 3, 7, 11, …. When p are any of these values, then $\frac{(p-1)}{2}$ is even, and hence $(-1/p) \equiv 1 \pmod 4$. Suppose that $p \equiv 3 \pmod 4$, that is p = 5, 13, 19, …, then $\frac{p-1}{2}$ is odd, and hence $(-1/p) \equiv -1 \pmod p$. Hence our proof is complete.

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

## Theorem 2: If p is an odd prime then (2/p) = 1 if p ≡ 1 (mod 8) or p ≡ 7 (mod 8) and (2/p) = -1 if p ≡ 3 (mod 8) or p ≡ 5 (mod 8).

We will summarize this theorem using the following diagram for the Legendre symbol (2/p):

(2/p) = 1 | (2/p) = -1 | (2/p) = -1 | (2/p) = 1 |
---|---|---|---|

$p \equiv 1 \pmod 8$ | $p \equiv 3 \pmod 8$ | $p \equiv 5 \pmod 8$ | $p \equiv 7 \pmod 8$ |

We will require Gauss's Lemma in order to prove this property of Legendre symbols. Please read this page before continuing this proof.

**Proof:**From Gauss's Lemma, we know that from the list of $2, 4, 6, ..., p - 1$ (all of which are least residues), then exactly g of them are greater than $\frac{p-1}{2}$.

- Suppose that 2m is the first even integer greater than $\frac{p-1}{2}$. Hence from the list, $2, 4, ..., 2(m - 1)$ are the integers in the list less than or equal to $\frac{p-1}{2}$, and $2m, 2(m+1), ..., p -1$ are the integers strictly greater than $\frac{p-1}{2}$. There are $\frac{p-1}{2}$ integers in this list all together, and $(m-1)$ integers less than $\frac{p-1}{2}$. Hence it follows that:

\begin{align} g = \frac{p-1}{2} - (m - 1) \end{align}

- Now we know that 2m is the smallest integer greater than $\frac{p-1}{2}$, so m is the smallest integers greater than $\frac{p-1}{4}$. So m - 1 is the smallest integer greater than $\frac{p-1}{4} - \frac{4}{4} = \frac{p - 5}{4}$.

- Furthermore, -(a - 1) is the largest integer less than $-\frac{p - 5}{4}$. Hence it follows that:

\begin{align} g = \frac{p-1}{2} - \frac{p - 5}{4} \\ g = \frac{p + 3}{4} \end{align}

- Hence if $p \equiv 1 \pmod 8$ or $p \equiv 7 \pmod 8$, then g is even and $(a/p) = (-1)^g = 1$. If $p \equiv 3 \pmod 8$ or $p \equiv 5 \pmod 8$, then g is odd, and $(a/p) = (-1)^g = -1$. Hence, the proof is complete, and:

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