Month: January 2020

In this post, we take a look at an interesting proof of the Quadratic Reciprocity theorem by Gotthold Eisenstein.

Definition: The Legendre symbol is a function $\left(\frac{a}{p}\right)$ which takes the values $\pm 1$ depending on whether $a$ is a quadratic residue modulo $p$. $\left(\frac{a}{p}\right) = \begin{cases}0 \quad \text{if }p|a \\ 1 \quad \text{if }a\text{ is a quadratic residue modulo }p \\ -1 \quad \text{if }a\text{ is a quadratic non-residue modulo }p\end{cases}$ Theorem (Quadratic Reciprocity Law): If $p$ and $q$ are distinct odd primes, then the quadratic reciprocity theorem states that the congruences $\begin{aligned} x^2 \equiv q \quad (\text{mod }p) \\ x^2 \equiv p \quad (\text{mod }q) \end{aligned}$ are both solvable or both unsolvable unless both $p$ and $q$ leave the the remainder $3$ when divided by $4$. Written symbolically, $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}$

We will start by proving two important results about quadratic residues that will be useful later on.

Lemma 1: Let $n\not\equiv 0 \;(\text{mod }p)$. Then $n$ is a quadratic residue modulo $p$ iff $n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p)$.

Proof: Fermat’s little theorem tells us that $n^{p-1}\equiv 1 \;(\text{mod }p)$ whenever $p \not| n$. Since, $n^{p-1}-1\equiv (n^{\frac{p-1}{2}}-1)(n^{\frac{p-1}{2}}+1)\equiv 0 \; (\text{mod }p)$ we have $n^{\frac{p-1}{2}}\equiv \pm 1\; (\text{mod }p)$. Therefore, it suffices to prove that $n$ is a quadratic residue modulo $p$ if and only if $n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p)$.

Suppose that $\left(\frac{n}{p} \right)=1$. Then, there is an integer $x$ such that $n\equiv x^2 \; (\text{mod p})$. Now, we have $n^{\frac{p-1}{2}}\equiv x^{p-1} \equiv 1 \equiv \left(\frac{n}{p} \right) \; (\text{mod }p)$

Conversely, assume that $n^{\frac{p-1}{2}}\equiv 1 \; (\text{mod }p)$. Let $g$ be a primitive root of $p$. Then, we have $n\equiv g^k \; (\text{mod }p)$ for some integer $k$. Since $n^{\frac{p-1}{2}}\equiv g^{\frac{k(p-1)}{2}} \equiv 1 \; (\text{mod }p)$, the order of $g$ must divide the exponent $\frac{k(p-1)}{2}$. Therefore, $p-1 | \frac{k(p-1)}{2}$ and thus $k$ is an even integer. Let’s say $k=2j$ for some integer $j$. Then, we have $n \equiv g^k \equiv g^{2j} \equiv (g^j)^2 \; (\text{mod }p)$ This proves that $n$ is a quadratic residue modulo $p$.

Lemma 2 (Gauss’s Lemma): For any odd prime $p$, let $a$ be an integer that is co-prime to $p$. Consider the integers $S = \left\{ a,\ 2a,\ 3a,\cdots, \frac{p-1}{2}a \right\}$ and their least positive residues modulo $p$. Let $n$ be the number of these residues that are greater than $p/2$. Then $\left(\frac{a}{p}\right)=(-1)^n$

Proof: Since $p\not | a$, none of the integers in $S$ are congruent to 0 and no two of them are congruent to each other modulo $p$. Let $r_1, \cdots, r_m$ be the residues modulo $p$ smaller than $\frac{p}{2}$, and let $s_1, \cdots, s_n$ be the residues modulo $p$ greater than $\frac{p}{2}$. Then $m+n=\frac{p-1}{2}$ and the integers $r_1, \cdots, r_m, p-s_1, \cdots , p-s_n$ are all positive and less than $\frac{p}{2}$. Now, we will prove that no two of these integers are equal. Suppose that for some choice of $i$ and $j$ we have $p-s_i = r_j$. We can choose integers $u$ and $v$, with $1 \leq u,v \leq \frac{p-1}{2}$ and satisfying $\begin{aligned} s_i &\equiv u a \; (\text{mod }p) \\ r_j &\equiv v a \; (\text{mod }p) \end{aligned}$ Now, we have $s_i+r_j \equiv a(u+v) \equiv p \equiv 0 \; (\text{mod }p)$ This implies that $u+v \equiv 0 \; (\text{mod }p)$. However, this is not possible because $1\leq u+v \leq p-1$. Thus, we have proven that the numbers $r_1,\cdots, r_m, p-s_1, \cdots p-s_n$ are simply a rearrangement of the integers $1,2,\cdots, \frac{p-1}{2}$. Their product is equal to $\left(\frac{p-1}{2} \right)!$. Therefore, $\begin{aligned} \left(\frac{p-1}{2}\right)! &= r_1 \cdots r_m (p-s_1)\cdots (p-s_n) \\ &\equiv (-1)^n r_1 \cdots r_m s_1\cdots s_n \; (\text{mod }p) \\ &\equiv (-1)^n a\cdot 2a\cdots \left(\frac{p-1}{2}\right)a \; (\text{mod }p) \\ &\equiv (-1)^n a^{\frac{p-1}{2}} \left( \frac{p-1}{2}\right)! \; (\text{mod }p) \end{aligned}$ The $\left( \frac{p-1}{2}\right)!$ term can be cancelled from both sides as $p\not| \left( \frac{p-1}{2}\right)!$. In other words, we have $a^{\frac{p-1}{2}}\equiv (-1)^n \; (\text{mod }p)$. This completes the proof of Gauss’s lemma.

We are now ready to prove the Quadratic reciprocity theorem.

Proof of the Quadratic Reciprocity Theorem:

Using the periodicity properties of $\sin$ and Gauss’s lemma, it is easy to verify the following result:

Lemma: Let $p$ and $q$ be distinct odd primes and let $A = \left\{ \alpha\in \mathbb{Z} | 1\leq \alpha \leq \frac{p-1}{2}\right\}$ be a half system modulo $p$. Then, $\left(\frac{q}{p}\right) = \prod_{\alpha\in A}\frac{\sin\left(\frac{2\pi}{p}q\alpha\right)}{\sin\left(\frac{2\pi}{p}\alpha\right)} \quad\quad (1)$

We start by examining the right hand side of equation $(1)$. The addition theorem for trigonometric functions yields $\sin 2\alpha = 2\sin\alpha\cos\alpha$ and $\sin 3\alpha = \sin\alpha(3-4\sin^2\alpha)$. Induction shows that $\sin q\alpha = \sin\alpha P(\sin\alpha)$ for all odd $q\geq 1$, where $P\in \mathbb{Z}[X]$ is a polynomial of degree $q-1$ and highest coefficient $(-4)^{\frac{q-1}{2}}$. Thus there exist $a_i \in \mathbb{Z}$ such that $\begin{aligned}\frac{\sin qz}{\sin z} &= (-4)^{\frac{q-1}{2}} \left( (\sin z)^{q-1}+a_{q-2} (\sin z)^{q-2}+\cdots + a_0 \right) \\ &= (-4)^{\frac{q-1}{2}} \psi(X), \quad \text{where }X=\sin z\end{aligned}$ Since $\phi(z)=\frac{\sin qz}{\sin z}$ is an even function, so is $\psi(X)$, hence $a_{q-2}=\cdots = a_1 = 0$. Now $\phi(z)$ has zeros $\left\{ \pm \frac{2\pi}{q}\beta, \ 1\leq \beta \leq \frac{q-1}{2}\right\}$. Since $\psi$ is monic of degree $q-1$, we may write $\psi(X) = \prod_{\beta\in B}\left(X^2-\sin^2\frac{2\pi\beta}{q} \right)$ where $B=\left\{1,\cdots,\frac{q-1}{2} \right\}$ is a half system modulo $q$. Replacing $X$ by $\sin z$, we get $\frac{\sin qz}{\sin z} = (-4)^{\frac{q-1}{2}} \prod_{\beta\in B }\left( \sin^2z -\sin^2\frac{2\pi\beta}{q}\right) \quad \quad (2)$ Put $z=\frac{2\pi\alpha}{p}$ in equation $(2)$ and plug the result into equation $(1)$. $\begin{aligned} \left(\frac{q}{p}\right) &= \prod_{\alpha\in A} (-4)^{\frac{q-1}{2}} \prod_{\beta\in B} \left( \sin^2\frac{2\pi\alpha}{p} -\sin^2\frac{2\pi\beta}{q}\right)\\ &= (-4)^{\frac{q-1}{2} \frac{p-1}{2}} \prod_{\alpha\in A}\prod_{\beta\in B} \left( \sin^2\frac{2\pi\alpha}{p} -\sin^2\frac{2\pi\beta}{q}\right)\quad\quad (3) \end{aligned}$ Exchanging $p$ and $q$ on the right side of $(3)$ give rise to factor of $(-1)^{(p-1)(q-1)/4}$. Therefore, $\left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}\left(\frac{p}{q}\right) \tag{4}$ which is the quadratic reciprocity law.

References

• Lemmermeyer, Franz. “Reciprocity Laws: From Euler to Eisenstein”. New York, Springer, 2000
• Burton, David M. “Elementary Number Theory”. New Delhi, Tata McGraw-Hill Publishing Company Limited, May 1 2006