Legendre Symbol Overview
students, this lesson introduces one of the most useful shortcuts in number theory for studying whether a number is a square modulo a prime. Squares modulo a number show up in cryptography, solving congruences, and pattern-finding in arithmetic 🔍. The Legendre symbol gives a compact way to answer a big question: for an odd prime $p$, is $a$ a quadratic residue modulo $p$?
By the end of this lesson, you should be able to:
- explain what the Legendre symbol means,
- decide whether a number is a quadratic residue modulo a prime using examples and rules,
- connect the symbol to the broader study of quadratic residues,
- and recognize how this idea helps organize information about squares modulo $p$.
What the Legendre Symbol Means
For an odd prime $p$ and an integer $a$, the Legendre symbol is written as $\left(\frac{a}{p}\right)$. It is defined by three possible values:
$$
$\left(\frac{a}{p}\right)=$
$\begin{cases}$
1 & \text{if } a \not$\equiv 0$ \pmod p \text{ and } a \text{ is a quadratic residue mod } p,\\
-1 & \text{if } a \text{ is not a quadratic residue mod } p,\\
0 & \text{if } a $\equiv 0$ \pmod p.
$\end{cases}$
$$
A quadratic residue modulo $p$ is a number congruent to a perfect square modulo $p$. In other words, $a$ is a quadratic residue mod $p$ if there exists some integer $x$ such that $x^2 \equiv a \pmod p$.
Example: modulo $7$, the squares are
$$
1^$2 \equiv 1$,\quad 2^2 $\equiv 4$,\quad 3^2 $\equiv 2$,\quad 4^2 $\equiv 2$,\quad 5^2 $\equiv 4$,\quad 6^2 $\equiv 1$ \pmod 7.
$$
So the nonzero quadratic residues mod $7$ are $1$, $2$, and $4$. That means
$$
$\left($$\frac{1}{7}$$\right)$=1,\quad $\left($$\frac{2}{7}$$\right)$=1,\quad $\left($$\frac{3}{7}$$\right)$=-1,\quad $\left($$\frac{4}{7}$$\right)$=1,\quad $\left($$\frac{5}{7}$$\right)$=-1,\quad $\left($$\frac{6}{7}$$\right)$=-1.
$$
This symbol is like a label that says “square,” “not a square,” or “zero mod $p$” ✅.
Why It Is Useful
The Legendre symbol compresses a lot of information into one small notation. Instead of listing every square modulo $p$, we can study patterns using algebraic rules.
This matters because checking directly whether $a$ is a square mod $p$ can be tedious when $p$ is large. For example, if $p=101$, testing every possible square by hand is not practical. The Legendre symbol helps simplify the problem and connects to deeper theorems.
It also appears in statements about solving equations like
$$
$ x^2 \equiv a \pmod p.$
$$
If $\left(\frac{a}{p}\right)=1$, then this congruence has a solution. If $\left(\frac{a}{p}\right)=-1$, then it does not. If $\left(\frac{a}{p}\right)=0$, then $p\mid a$.
So the symbol is not just notation; it is a decision tool.
Computing Squares Modulo a Prime
To understand the Legendre symbol, it helps to know how to list squares modulo a prime. Suppose $p$ is an odd prime. The numbers
$$
$1^2, 2^2, 3^2, \dots, \left(\frac{p-1}{2}\right)^2$
$$
produce all the nonzero quadratic residues modulo $p$, though some residues may appear more than once because $x^2 \equiv (-x)^2 \pmod p$.
For example, modulo $11$:
$$
$1^2 \equiv 1,$
$2^2 \equiv 4,$
$3^2 \equiv 9,$
$4^2 \equiv 5,$
$5^2 \equiv 3 \pmod{11}.$
$$
So the nonzero quadratic residues modulo $11$ are $1,3,4,5,9.
That means:
$$
$\left($$\frac{1}{11}$$\right)$=1,\quad $\left($$\frac{2}{11}$$\right)$=-1,\quad $\left($$\frac{3}{11}$$\right)$=1,\quad $\left($$\frac{4}{11}$$\right)$=1,\quad $\left($$\frac{5}{11}$$\right)$=1,\quad $\left($$\frac{6}{11}$$\right)$=-1.
$$
A good habit is to reduce $a$ modulo $p$ first. Since the symbol depends only on the residue class of $a$ modulo $p$, we have
$$
$\left($$\frac{a}{p}$$\right)$=$\left($$\frac{b}{p}$$\right)$ \quad \text{whenever } a$\equiv$ b \pmod p.
$$
So $\left(\frac{22}{11}\right)=\left(\frac{0}{11}\right)=0$, and $\left(\frac{15}{11}\right)=\left(\frac{4}{11}\right)=1$.
Basic Rules of the Legendre Symbol
The Legendre symbol has a few important properties that make it powerful:
1. Multiplicative property
For integers $a$ and $b$,
$$
$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$
$$
This means you can break a product into smaller pieces.
Example: To find $\left(\frac{10}{13}\right)$, write $10=2\cdot 5$. Then
$$
$\left(\frac{10}{13}\right)=\left(\frac{2}{13}\right)\left(\frac{5}{13}\right).$
$$
If you know the values of the smaller symbols, you can combine them.
2. Squares give $1$
If $a\not\equiv 0 \pmod p$ and $a\equiv x^2 \pmod p$ for some $x$, then
$$
$\left(\frac{a}{p}\right)=1.$
$$
This is exactly what the symbol is designed to detect.
3. Zero when divisible by $p$
If $p\mid a$, then
$$
$\left(\frac{a}{p}\right)=0.$
$$
This makes the symbol complete: every integer gives one of the three values $-1$, $0$, or $1$.
4. Depends only on the class mod $p$
If $a\equiv b\pmod p$, then
$$
$\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).$
$$
This is why modular reduction is so useful.
A Famous Shortcut: Euler’s Criterion
One of the biggest reasons the Legendre symbol is important is Euler’s criterion. For an odd prime $p$ and an integer $a$ with $p\nmid a$,
$$
$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p.$
$$
More precisely,
$$
$ a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p,$
$$
where the right side is interpreted as $1$ or $-1$ modulo $p$.
This means:
- if $a^{(p-1)/2} \equiv 1 \pmod p$, then $a$ is a quadratic residue,
- if $a^{(p-1)/2} \equiv -1 \pmod p$, then $a$ is not a quadratic residue.
Example: Let $p=7$ and $a=2$. Then
$$
$2^{(7-1)/2}=2^3=8\equiv 1 \pmod 7.$
$$
So
$$
$\left(\frac{2}{7}\right)=1.$
$$
This matches what we found by listing squares modulo $7$.
Euler’s criterion is useful because it turns a residue question into exponentiation, which is often easier to handle systematically.
Worked Examples
Example 1: Is $3$ a quadratic residue modulo $11$?
From the list of squares modulo $11$, we saw that $3$ appears as $5^2 \equiv 3 \pmod{11}$. Therefore
$$
$\left(\frac{3}{11}\right)=1.$
$$
Example 2: Is $2$ a quadratic residue modulo $7$?
We found that $3^2 \equiv 2 \pmod 7$, so
$$
$\left(\frac{2}{7}\right)=1.$
$$
Example 3: Is $6$ a quadratic residue modulo $7$?
The residues mod $7$ are $1,2,4$. Since $6 is not on the list,
$$
$\left(\frac{6}{7}\right)=-1.$
$$
Example 4: Evaluate $\left(\frac{14}{7}\right)$
Since $14\equiv 0\pmod 7$,
$$
$\left(\frac{14}{7}\right)=0.$
$$
These examples show the three possible outcomes in action.
How It Fits into Quadratic Residues Overview
The Legendre symbol is a compact language for the study of quadratic residues modulo an odd prime. In the larger topic of quadratic residues, students often begin by listing squares modulo small primes. That builds intuition. The Legendre symbol then gives a formal notation that can describe the same idea more efficiently.
It also prepares the way for deeper results such as the law of quadratic reciprocity, which studies relationships between symbols like $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$ for odd primes $p$ and $q$. Before reaching that advanced idea, it is important to understand the meaning of a single Legendre symbol and how it tells whether a number is a square mod $p$.
So, in the big picture, the Legendre symbol is the bridge between simple square-checking and advanced residue theory 📘.
Conclusion
students, the main idea to remember is this: for an odd prime $p$, the Legendre symbol $\left(\frac{a}{p}\right)$ tells you whether $a$ is a quadratic residue modulo $p$. Its values are $1$, $-1$, or $0$, and each value has a clear meaning. You can compute it by listing squares, reducing modulo $p$, using multiplicative properties, or applying Euler’s criterion.
This symbol is a key part of quadratic residues because it organizes the question “Is $a$ a square mod $p$?” into a neat mathematical tool. Once you understand it, you are ready for more advanced ideas in number theory.
Study Notes
- The Legendre symbol is written as $\left(\frac{a}{p}\right)$, where $p$ is an odd prime.
- Its values are:
- $1$ if $a$ is a nonzero quadratic residue mod $p$,
- $-1$ if $a$ is not a quadratic residue mod $p$,
- $0$ if $a\equiv 0\pmod p$.
- A quadratic residue modulo $p$ is a number congruent to a square modulo $p$.
- If $a\equiv b\pmod p$, then $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.
- The symbol is multiplicative:
$$
$ \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$
$$
- Euler’s criterion says that for $p\nmid a$,
$$
$ a^{(p-1)/2}\equiv \left(\frac{a}{p}\right) \pmod p.$
$$
- The Legendre symbol is a main tool in quadratic residue theory and leads toward quadratic reciprocity.