5.5: Legendre Symbol

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 and Attributions

• 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.