$$\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.6: The Law of Quadratic Reciprocity

• • 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}}}$$

Given that $$p$$ and $$q$$ are odd primes. Suppose we know whether $$q$$ is a quadratic residue of $$p$$ or not. The question that this section will answer is whether $$p$$ will be a quadratic residue of $$q$$ or not. Before we state the law of quadratic reciprocity, we will present a Lemma of Eisenstein which will be used in the proof of the law of reciprocity. The following lemma will relate Legendre symbol to the counting lattice points in the triangle.

Lemma of Eisenstein

If $$p\neq 2$$ is a prime and $$a$$ is an odd integer such that $$p\nmid a$$, then

$\left(\frac{a}{p}\right)=(-1)^{\sum_{i=1}^{(p-1)/2}[ia/p]}.$

Consider the least positive residues of the integers $$a, 2a,...,((p-1)/2)a$$; let $$m_1,m_2,...,m_s$$ be integers of this set such that $$m_i>p/2$$ for all $$i$$ and let $$n_1,n_2,...,n_t$$ be those integers where $$n_i<p/2$$. Using the division algorithm, we see that $ia=p[ia/p]+r$ where $$r$$ is one of the $$m_i$$ or $$n_i$$. By adding the $$(p-1)/2$$ equations, we obtain

$\label{qr1} \sum_{i=1}^{(p-1)/2}ia=\sum_{i=1}^{(p-1)/2}p[ia/p]+\sum_{i=1}^sm_i+\sum_{i=1}^tn_i.$

As in the proof of Gauss’s Lemma, we see that $p-m_1,p-m_2,...,p-m_s,p-n_1,p-n_2,...,p-n_t$ are precisely the integers $$1,2,...,(p-1)/2$$, in the same order. Now we obtain

$\label{qr2} \sum_{i=1}^{(p-1)/2}i=\sum_{i=1}^s(p-m_i)+\sum_{i=1}^tn_i=ps-\sum_{i=1}^sm_i+\sum_{i=1}^tn_i.$ We subtract $$(\ref{qr2})$$ from $$(\ref{qr1})$$ to get $\sum_{i=1}^{(p-1)/2}ia-\sum_{i=1}^{(p-1)/2}i=\sum_{i=1}^{(p-1)/2}p[ia/p]-ps+2\sum_{i=1}^sm_i.$

Now since we are taking the following as exponents for $$-1$$, it suffice to look at them modulo 2. Thus

$0\equiv \sum_{i=1}^{(p-1)/2}[ia/p]-s(mod \ 2).$ $\sum_{i=1}^{(p-1)/2}[ia/p]\equiv s(mod \ 2)$ Using Gauss’s lemma, we get

$\left(\frac{a}{p}\right)=(-1)^s=(-1)^{\sum_{i=1}^{(p-1)/2}[ia/p]}.$

Let $$p$$ and $$q$$ be distinct odd primes. Then

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}.\frac{q-1}{2}}$

We consider now the pairs of integers also known as lattice points $$(x,y)$$ with $1\leq x\leq (p-1)/2 \mbox{and} \ \ 1\leq y\leq (q-1)/2.$ The number of such pairs is $$\frac{p-1}{2}.\frac{q-1}{2}$$. We divide these pairs into two groups depending on the sizes of $$qx$$ and $$py$$. Note that $$qx\neq py$$ for all pairs because $$p$$ and $$q$$ are distinct primes.

We now count the pairs of integers $$(x,y)$$ with $1\leq x\leq (p-1)/2, \ \ 1\leq y\leq (q-1)/2 \mbox{and} \ \ qx>py.$ Note that these pairs are precisely those where

$1\leq x\leq (p-1)/2 \mbox{and} \ \ 1\leq y\leq qx/p.$

For each fixed value of $$x$$ with $$1\leq x\leq (p-1)/2$$, there are $$[qx/p]$$ integers satisfying $$1\leq y\leq qx/p$$. Consequently, the total number of pairs with are

$1\leq x\leq (p-1)/2, \ \ 1\leq y\leq qx/p, \mbox{and} \ \ qx>py$ is $\sum_{i=1}^{(p-1)/2}[qi/p].$

Consider now the pair of integers $$(x,y)$$ with

$1\leq x\leq (p-1)/2, \ \ 1\leq y\leq (q-1)/2, \mbox{and} \ \ qx<py.$

Similarly, we find that the total number of such pairs of integers is

$\sum_{i=1}^{(q-1)/2}[pi/q].$

Adding the numbers of pairs in these classes, we see that $\sum_{i=1}^{(p-1)/2}[qi/p]+ \sum_{i=1}^{(q-1)/2}[pi/q]=\frac{p-1}{2}.\frac{q-1}{2},$ and hence using Lemma 14, we get that

$\left(\frac{p}{q}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}.\frac{q-1}{2}}$

Exercises

1. Evaluate $$\left(\frac{3}{53}\right)$$.

2. Evaluate $$\left(\frac{31}{641}\right)$$.

3. Using the law of quadratic reciprocity, show that if $$p$$ is an odd prime, then $\left(\frac{3}{p}\right)=\left\{\begin{array}{lcr} \ 1 &{\mbox{if}\ p\equiv \pm1(mod \ 12)} \\ \ -1 &{\mbox{if}\ p\equiv \pm 5(mod \ 12)}. \\ \end{array}\right .$

4. Show that if $$p$$ is an odd prime, then $\left(\frac{-3}{p}\right)=\left\{\begin{array}{lcr} \ 1 &{\mbox{if}\ p\equiv 1(mod \ 6)} \\ \ -1 &{\mbox{if}\ p\equiv -1 (mod \ 6)}. \\ \end{array}\right .$

5. Find a congruence describing all primes for which 5 is a quadratic residue.

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