In this post, we take a look at an interesting proof of the Quadratic Reciprocity theorem by Gotthold Eisenstein. <\/p>\n
\n Definition:<\/b> 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$. \n$$\\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}$$\nTheorem (Quadratic Reciprocity Law):<\/b> 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}$$\n<\/p>\n
\nWe will start by proving two important results about quadratic residues that will be useful later on. <\/p>\n\n\n\n
Lemma 1:<\/b> 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)$. <\/p>\n
\nProof:<\/b> Fermat’s little theorem tells us that $n^{p-1}\\equiv 1 \\;(\\text{mod }p)$ whenever $p \\not| n$. Since,\n$$n^{p-1}-1\\equiv (n^{\\frac{p-1}{2}}-1)(n^{\\frac{p-1}{2}}+1)\\equiv 0 \\; (\\text{mod }p)$$\nwe 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)$.\n<\/p>\n
\nSuppose 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$$n^{\\frac{p-1}{2}}\\equiv x^{p-1} \\equiv 1 \\equiv \\left(\\frac{n}{p} \\right) \\; (\\text{mod }p)$$\n<\/p>\n
\nConversely, 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$$n \\equiv g^k \\equiv g^{2j} \\equiv (g^j)^2 \\; (\\text{mod }p)$$\nThis proves that $n$ is a quadratic residue modulo $p$. \n
\n\n\n\n
\nLemma 2 (Gauss’s Lemma):<\/b> For any odd prime $p$, let $a$ be an integer that is co-prime to $p$. Consider the integers \n$$S = \\left\\{ a,\\ 2a,\\ 3a,\\cdots, \\frac{p-1}{2}a \\right\\}$$\nand 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$$\n<\/p>\n
\nProof:<\/b> 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 \n$$ r_1, \\cdots, r_m, p-s_1, \\cdots , p-s_n $$\nare 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\n$$\n\\begin{aligned}\ns_i &\\equiv u a \\; (\\text{mod }p) \\\\\nr_j &\\equiv v a \\; (\\text{mod }p)\n\\end{aligned}\n$$\nNow, we have\n$$ s_i+r_j \\equiv a(u+v) \\equiv p \\equiv 0 \\; (\\text{mod }p) $$\nThis 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, \n$$\n\\begin{aligned}\n\\left(\\frac{p-1}{2}\\right)! &= r_1 \\cdots r_m (p-s_1)\\cdots (p-s_n) \\\\\n&\\equiv (-1)^n r_1 \\cdots r_m s_1\\cdots s_n \\; (\\text{mod }p) \\\\\n&\\equiv (-1)^n a\\cdot 2a\\cdots \\left(\\frac{p-1}{2}\\right)a \\; (\\text{mod }p) \\\\\n&\\equiv (-1)^n a^{\\frac{p-1}{2}} \\left( \\frac{p-1}{2}\\right)! \\; (\\text{mod }p)\n\\end{aligned}\n$$\nThe $\\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.\n<\/p>\n
We are now ready to prove the Quadratic reciprocity theorem.<\/p>\n\n\n\n
\nProof of the Quadratic Reciprocity Theorem:<\/b><\/p>
\nUsing the periodicity properties of $\\sin$ and Gauss’s lemma, it is easy to verify the following result:\n<\/p>\nLemma:<\/b> 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)$$\n
\nWe 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 \n$$ \\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} $$ \nSince $\\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 \n$$ \\psi(X) = \\prod_{\\beta\\in B}\\left(X^2-\\sin^2\\frac{2\\pi\\beta}{q} \\right) $$\nwhere $B=\\left\\{1,\\cdots,\\frac{q-1}{2} \\right\\}$ is a half system modulo $q$. Replacing $X$ by $\\sin z$, we get \n$$ \\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)$$ \nPut $z=\\frac{2\\pi\\alpha}{p}$ in equation $(2)$ and plug the result into equation $(1)$. \n$$ \\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} $$ \nExchanging $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.\n<\/p>\n
\n
In this post, we present an interesting proof of the Quadratic Reciprocity theorem given by Gotthold Eisenstein. Continue reading