$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 5.5: Legendre Symbol

• • Contributed by Wissam Raji
• Associate Professor and the Chairman (Mathematics) at American University of Beirut

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

In this section, we define Legendre symbol which is a notation associated to quadratic residues and prove related theorems.

Definition: Legendre symbol

Let $$p\neq 2$$ be a prime and $$a$$ be an integer such that $$p\nmid a$$. The Legendre symbol $$\left(\frac{a}{p}\right)$$ is defined by

$\left(\frac{a}{p}\right)=\left\{\begin{array}{lcr} \ 1 &\mbox{if a is a quadratic residue of p} \\ \ -1 &\mbox{if a is a quadratic nonresidue of p}. \\ \end{array}\right .$

Notice that using the previous example, we see that

\begin{aligned} && \left(\frac{1}{7}\right)=\left(\frac{2}{7}\right)=\left(\frac{4}{7}\right)=1\\ && \left(\frac{3}{7}\right)=\left(\frac{5}{7}\right)=\left(\frac{6}{7}\right)=-1\end{aligned}

In the following theorem, we present a way to determine wether an integer is a quadratic residue of a prime.

Euler’s Criterion

Let $$p\neq 2$$ be a prime and let $$a$$ be a positive integer such that $$p\nmid a$$. Then

$\left(\frac{a}{p}\right)\equiv a^{\phi(p)/2}(mod \ p).$

Assume that $$\left(\frac{a}{p}\right)=1$$. Then the congruence $$x^2\equiv a(mod \ p)$$ has a solution say $$x=x'$$. According to Fermat’s theorem, we see that

$a^{\phi(p)/2}=((x')^2)^{\phi(p)/2}\equiv 1(mod\ p).$

Now if $$\left(\frac{a}{p}\right)=-1$$, then $$x^2\equiv a(mod \ p)$$ is not solvable. Thus by Theorem 26, we have that for each integer k with $$(k,p)=1$$ there is an integer $$l$$ such that $$kl\equiv a(mod \ p)$$. Notice that $$i\neq j$$ since $$x^2\equiv a(mod \ p)$$ has no solutions. Thus we can couple the integers $$1,2,...,p-1$$ into $$(p-1)/2$$ pairs, each has product $$a$$. Multiplying these pairs together, we find out that

$(p-1)!\equiv a^{\phi(p)/2}(mod \ p).$

Using Wilson’s Theorem, we get $\left(\frac{a}{p}\right)=-1\equiv a^{(p-1)/2}(mod \ p).$

Let $$p=13$$ and $$a=3$$. Then $$\left(\frac{3}{13}\right)=-1\equiv 3^{6}(mod \ 13).$$

We now prove some properties of Legendre symbol.

Let $$p\neq 2$$ be a prime. Let $$a$$ and $$b$$ be integers such that $$p\nmid a$$, $$p\nmid b$$ and $$p\mid (a-b)$$ then $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).$

Since $$p\mid (a-b)$$, then $$x^2\equiv a(mod \ p)$$ has a solution if and only if $$x^2\equiv b(mod \ p)$$ has a solution. Hence $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$

Let $$p\neq 2$$ be a prime. Let $$a$$ and $$b$$ be integers such that $$p\nmid a$$, $$p\nmid b$$ then $\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)$

By Euler’s criterion, we have $\left(\frac{a}{p}\right)\equiv a^{\phi(p)/2}(mod \ p)$ and $\left(\frac{b}{p}\right)\equiv b^{\phi(p)/2}(mod \ p).$ Thus we get $\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \equiv (ab)^{\phi(p)/2}\equiv \left(\frac{ab}{p}\right)(mod \ p).$ We now show when is $$-1$$ a quadratic residue of a prime $$p$$ .

If $$p\neq 2$$ is a, then $\left(\frac{-1}{p}\right)=\left\{\begin{array}{lcr} \ 1 &{\mbox{if}\ p\equiv 1(mod \ 4)} \\ \ -1 &{\mbox{if}\ p\equiv -1(mod \ 4)}. \\ \end{array}\right .$

By Euler’s criterion, we know that $\left(\frac{a}{p}\right)=(-1)^{\phi(p)/2}(mod \ p)$ If $$4\mid (p-1)$$, then $$p=4m+1$$ for some integer $$m$$ and thus we get $(-1)^{\phi(p)/2}=(-1)^{2m}=1.$ and if $$4\mid (p-3)$$, then $$p=4m+3$$ for some integer $$m$$ and we also get $(-1)^{\phi(p)/2}=(-1)^{2m+1}=-1.$

We now determine when $$2$$ is a quadratic residue of a prime $$p$$.

For every odd prime $$p$$ we have

$\left(\frac{2}{p}\right)=\left\{\begin{array}{lcr} \ 1 &{\mbox{if}\ p\equiv \pm1(mod \ 8)} \\ \ -1 &{\mbox{if}\ p\equiv \pm 3(mod \ 8)}. \\ \end{array}\right .$

Consider the following $$(p-1)/2$$ congruences

\begin{aligned} p-1&\equiv& 1(-1)^1 \ \ \ (mod \ p)\\ 2&\equiv& 2(-1)^2 \ \ \ (mod \ p)\\ p-3&\equiv& 3(-1)^3 \ \ \ (mod \ p)\\ 4&\equiv& 4(-1)^4 \ \ \ (mod \ p)\\ &.& \\ &.& \\ &.& \\ r&\equiv& \frac{p-1}{2}(-1)^{(p-1)/2} \ \ \ (mod \ p),\\\end{aligned}

where $$r$$ is either $$p-(p-1)/2$$ or $$(p-1)/2$$. Multiplying all these equations we get,

$2.4.6...(p-1)\equiv \left(\frac{p-1}{2}\right)!(-1)^{1+2+...+(p-1)/2} \ \ \ (mod \ p).$

This gives us

$2^{(p-1)/2}\left(\frac{p-1}{2}\right)! \equiv \left(\frac{p-1}{2}\right)!(-1)^{(p^2-1)/8} (mod \ p).$

Now notice that $$\left(\frac{p-1}{2}\right)!\not\equiv 0(mod \ p)$$ and thus we get

$2^{(p-1)/2}\equiv (-1)^{(p^2-1)/8}(mod \ p).$

Note also that by Euler’s criterion, we get

$2^{\phi(p)/2}\equiv \left(\frac{2}{p}\right)(mod \ p),$

and since each member is 1 or -1 the two members are equal.

We now present an important lemma that determines whether an integer is a quadratic residue of a prime or not.

Gauss’s Lemma

Let $$p\neq 2$$ be a prime and $$a$$ a relatively prime integer to $$p$$. If $$k$$ counts the number of least positive residues of the integers $$a, 2a,...,((p-1)/2)a$$ that are greater than $$p/2$$, then

$\left(\frac{a}{p}\right)=(-1)^k.$

Let $$m_1,m_2,...,m_s$$ be those integers greater than $$p/2$$ in the set of the least positive residues of the integers $$a, 2a,...,((p-1)/2)a$$ and let $$n_1,n_2,...,n_t$$ be those less than $$p/2$$. We now show that

$p-m_1,p-m_2,...,p-m_k,p-n_1,p-n_2,...,p-n_t$

are precisely the integers $1,2,...,(p-1)/2,$ in the same order.

So we shall show that no two integers of these are congruent modulo $$p$$, because there are exactly $$(p-1)/2$$ numbers in the set, and all are positive integers less than or equal to $$(p-1)/2$$. Notice that $$m_i\not\equiv m_j (\mod \ p)$$ for all $$i\neq j$$ and $$n_i\not\equiv n_j (\mod \ p)$$ for all $$i\neq j$$. If any of these congruences fail, then we will have that $$r\equiv s(mod \ p)$$ assuming that $$ra\equiv sa(mod \ p)$$. Also any of the integers $$p-m_i$$ can be congruent to any of the $$n_i$$’s. Because if such congruence holds, then we have $$ra\equiv p-sa(mod \ p)$$, so that $$ra\equiv -sa(mod \ p)$$. Because $$p\nmid a$$, this implies that $$r\equiv -s(mod \ p)$$, which is impossible. We conclude that

$\prod_{i=1}^k(p-m_i)\prod_{i=1}^tn_i\equiv \left(\frac{p-1}{2}\right)!(mod \ p),$

which implies

$(-1)^sm_1m_2...(p-m_k)n_1n_2...n_t\equiv \left(\frac{p-1}{2}\right)!(mod \ p),$

Simplifying, we get

$m_1m_2...(p-m_k)n_1n_2...n_t\equiv a.2a...((p-1)/2)= a^{(p-1)/2}((p-1)/2)!( mod \ p).$

As a result, we have that

$a^{(p-1)/2}((p-1)/2)!\equiv ((p-1)/2)!(mod \ p)$

Note that since $$(p,((p-1)/2)!)=1$$, we get

$(-1)^ka^{(p-1)/2}\equiv 1(mod \ p).$

Thus we get

$a^{(p-1)/2}\equiv(-1)^k(mod \ p).$

Using Euler’s criterion, the result follows.

To find $$\left(\frac{5}{13}\right)$$ using Gauss’s lemma, we calculate

$\sum_{i=1}^6[5i/13]=[5/13]+[10/13]+[15/13]+[20/13]+[25/13]+[30/13]=5$ Thus we get $$\left(\frac{5}{13}\right)=(-1)^5=-1$$.

Exercises

1. Find all quadratic residues of 3

2. Find all quadratic residues of 19.

3. Find the value of Legendre symbol $$\left(\frac{j}{7}\right)$$ for $$j=1,2,3,4,5,6$$.

4. Evaluate the Legendre symbol $$\left(\frac{7}{11}\right)$$by using Euler’s criterion.

5. Let $$a$$ and $$b$$ be integers not divisible by $$p$$. Show that either one or all three of the integers $$a,b$$ and $$ab$$ are quadratic residues of $$p$$.

6. Let $$p$$ be a prime and $$a$$ be a quadratic residue of $$p$$. Show that if $$p\equiv 1(mod \ 4)$$, then $$-a$$ is also a quadratic residue of $$p$$, whereas if $$p\equiv 3(mod \ 4)$$, then $$-a$$ is a quadratic nonresidue of $$p$$.

7. Show that if $$p$$ is an odd prime and a is an integer not divisible by $$p$$ then $$\left(\frac{a^2}{p}\right)=1$$.

## Contributors

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.