LearnMathOnline

For any two distinct odd primes \(p\) and \(q\), the Legendre symbols \(\displaystyle\left(\frac{p}{q}\right)\) and \(\displaystyle\left(\frac{q}{p}\right)\) are defined. What is the relation between them? In other words do we know whether \(x^2 \equiv q \:\left(\mathrm{mod}\: p \right)\) has a solution once we know \(x^2 \equiv p \:\left(\mathrm{mod}\: q \right)\) has a solution? The answer is given by the Quadratic Reciprocity Law which was referred as the "golden theorem" by Gauss who gave its first proof.

Theorem.(Quadratic Reciprocity Law) For any two distinct odd primes \(p\) and \(q\), \[\displaystyle\left(\frac{p}{q} \right) \displaystyle\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.\]

Proof. 1. Note that \(p \equiv 1 \:\left(\mathrm{mod}\:4\right) \iff (p-1)/2\) is even and \(p \equiv 3 \:\left(\mathrm{mod}\:4 \right) \iff (p-1)/2\) is odd. If \(p \equiv 1 \:\left(\mathrm{mod}\:4 \right)\) or \(q \equiv 1 \:\left(\mathrm{mod}\:4 \right)\), then \(\frac{p-1}{2}\cdot\frac{q-1}{2}\) is an even integer and consequently \(\displaystyle\left(\frac{p}{q}\right) \displaystyle\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}=1\). Similarly if \(p\equiv q \equiv 3 \:\left(\mathrm{mod}\: 4\right)\), then \(\frac{p-1}{2}\cdot\frac{q-1}{2}\) is an odd integer and consequently \(\displaystyle\left(\frac{p}{q}\right) \displaystyle\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}=-1\).

2. It follows from (1) by multiplying the equation by \(\displaystyle\left(\frac{q}{p}\right)\) and using \(\displaystyle\left(\frac{q}{p}\right)^2=1\). ◼

For a general strategy to find \(\displaystyle\left(\frac{a}{p}\right)\), consider the unique prime-power factorization of \(a=\pm 2^{\alpha_1} p_2^{\alpha_2}\cdots p_k^{\alpha_k}\). By the multiplicative property of the Legendre symbol, \[\displaystyle\left(\frac{a}{p}\right)=\displaystyle\left(\frac{\pm 2^{\alpha_1} p_2^{\alpha_2}\cdots p_k^{\alpha_k}}{p}\right) =\displaystyle\left(\frac{\pm 1}{p}\right) \displaystyle\left(\frac{2}{p}^{\alpha_1}\right) \displaystyle\left(\frac{p_2}{p}^{\alpha_2}\right)\cdots \displaystyle\left(\frac{p_k}{p}^{\alpha_k}\right).\] Note that \(\displaystyle\left(\frac{\pm 1}{p}\right)\) is known and \(\displaystyle\left(\frac{p_i}{p}\right)\) can be found by the Quadratic Reciprocity Law where \(\displaystyle\left(\frac{2}{p}\right)\) is obtained (from Gauss's Law) by the following:

Theorem. For any odd prime \(p\), \(\displaystyle\left(\frac{2}{p}\right)=1\) if and only if \(p\equiv \pm 1 \:\left(\mathrm{mod}\:8 \right)\).

Example. Let us find \(\displaystyle\left(\frac{-41}{103}\right)\). Note that \(41\) and \(103\) are odd primes. \[ \begin{array}{rll} \displaystyle\left(\frac{-41}{103}\right)&=\displaystyle\left(\frac{-1}{103}\right)\displaystyle\left(\frac{41}{103}\right) & \\ &=(-1)^{(103-1)/2}\displaystyle\left(\frac{41}{103}\right) & \\ &=(-1)\displaystyle\left(\frac{103}{41}\right) & \text{ by QRL as } 41\equiv 1 \:\left(\mathrm{mod}\:4\right)\\ &=-\displaystyle\left(\frac{21}{41}\right) & \text{ since } 103\equiv 21 \:\left(\mathrm{mod}\:41\right)\\ &=-\displaystyle\left(\frac{3}{41}\right)\displaystyle\left(\frac{7}{41}\right) & \text{ since } 21=3\cdot 7\\ &=-\displaystyle\left(\frac{41}{3}\right)\displaystyle\left(\frac{41}{7}\right) & \text{ by QRL as } 41\equiv 1 \:\left(\mathrm{mod}\:4\right)\\ &=-\displaystyle\left(\frac{2}{3}\right)\displaystyle\left(\frac{-1}{7}\right) & \text{ since } 41\equiv 2 \:\left(\mathrm{mod}\:3\right),\; 41\equiv -1 \:\left(\mathrm{mod}\:7\right) \\ &=-(-1)(-1)^{(7-1)/2} & \text{ since } 3\not\equiv \pm 1 \:\left(\mathrm{mod}\:8\right) \\ &=-1. & \end{array}\] Thus \(x^2 \equiv -41 \:\left(\mathrm{mod}\:103\right)\) has no solution.

There are hundreds of proofs of the Quadratic Reciprocity Law like that of Pythagorean Theorem. The most traditional one uses Gauss's Lemma and its corollary by Eisenstein.

Theorem. Let \(p\) be an odd prime and \(a\) be an integer not divisible by \(p\). Let \[ S=\left\lbrace a,2a,3a,\ldots,\frac{p-1}{2}a \right\rbrace.\] If \(n\) is the number of integers of \(S\) whose least positive residues modulo \(p\) are greater than \(p/2\), then \[\displaystyle\left(\frac{a}{p}\right)=(-1)^n. \:\: (\text{Gauss's Lemma})\] Moreover, if \(a\) is odd, then \[ n\equiv \sum_{k=1}^{(p-1)/2}\left\lfloor \frac{ka}{p}\right\rfloor \:\left(\mathrm{mod}\:2\right),\] and consequently \[\displaystyle\left(\frac{a}{p}\right)=(-1)^{\displaystyle\sum_{k=1}^{(p-1)/2}} \left\lfloor \frac{ka}{p} \right\rfloor . \:\: (\text{Eisenstein's Lemma}) \]

Example. Let \(p=13\) and \(a=7\). Then \((p-1)/2=6\) and \[ S=\left\lbrace a,2a,3a,4a,5a,6a \right\rbrace =\left\lbrace 7,14,21,28,35,42 \right\rbrace.\] The least positive residues of integers of \(S\) modulo \(p=13\) are \(\left\lbrace {\bf 7},1,{\bf 8},2,{\bf 9},3 \right\rbrace.\) If \(n\) is the number of integers of \(S\) whose least positive residues modulo \(p=13\) are greater than \(p/2=6.5\), then \(n=3\). The following verifies Gauss's Lemma: \[\displaystyle\left(\frac{a}{p}\right)=\displaystyle\left(\frac{7}{13}\right)=-1=(-1)^3=(-1)^n.\] The following verifies Eisenstein's Lemma: \[\begin{array}{rl}\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p} \right\rfloor &=\sum_{k=1}^{6} \left\lfloor \frac{7k}{13} \right\rfloor\\ &= \left\lfloor \frac{7}{13} \right\rfloor +\left\lfloor \frac{14}{13} \right\rfloor +\left\lfloor \frac{21}{13}\right\rfloor +\left\lfloor \frac{28}{13} \right\rfloor +\left\lfloor \frac{35}{13} \right\rfloor +\left\lfloor \frac{42}{13} \right\rfloor\\ &=9 \\ &\equiv n \:\left(\mathrm{mod}\: 2\right). \end{array}\] \[\displaystyle\left(\frac{a}{p}\right)=\displaystyle\left(\frac{7}{13}\right)=-1=(-1)^9=(-1)^{\sum_{k=1}^{(p-1)/2}} \left\lfloor \frac{ka}{p} \right\rfloor.\]

Proof. First note that no integer in \(S\) is congruent to \(0\) modulo \(p\) and no two integers in \(S\) are congruent modulo \(p\) (Why?). Let \(r_1,r_2,\ldots,r_m,s_1,s_2,\ldots,s_n\) be the least positive residues of integers in \(S\) modulo \(p\) where \(m+n=(p-1)/2 \) and \[ r_1 < r_2 <\cdots< r_m <\frac{p}{2}< s_1< s_2<\cdots< s_n.\] Since \(p > s_i > p/2\), \(0< p-s_i < p/2\) for \(i=1,2,\ldots,n\). Now we show that \[\left\lbrace r_1,r_2,\ldots,r_m,p-s_1,p-s_2,\ldots,p-s_n \right\rbrace=\left\lbrace 1,2,3,\ldots,\frac{p-1}{2} \right\rbrace.\] Note that since \(p-s_1,p-s_2,\ldots,p-s_n\) are distinct positive integers less than \(p/2\) and so are \(r_1,r_2,\ldots,r_m\), it suffices to show that \(p-s_i\neq r_j\). Suppose \(p-s_i= r_j\). Note that \(s_i\equiv xa \:\left(\mathrm{mod}\: p \right)\) and \(r_j\equiv ya \:\left(\mathrm{mod}\: p \right)\) for some positive integers \(x,y\leq \frac{p-1}{2}\). Then \[(x+y)a \equiv s_i+ r_j =p\equiv 0\:\left(\mathrm{mod}\: p\right),\] which implies \(p\vert (x+y)a\). Since \(p\nmid a\), \(p\vert (x+y)\), a contradiction as \(1 < x+y\leq p-1\). Thus \[ \begin{eqnarray*} &1\cdot 2\cdot 3\cdots\frac{p-1}{2} &= r_1\cdot r_2\cdots r_m\cdot (p-s_1)\cdot (p-s_2)\cdots(p-s_n)\\ \implies & \left(\frac{p-1}{2}\right)! &= r_1\cdot r_2\cdots r_m\cdot (p-s_1)\cdot (p-s_2)\cdots(p-s_n)\\ & &\equiv r_1\cdot r_2\cdots r_m\cdot (-s_1)\cdot (-s_2)\cdots(-s_n) \:\left(\mathrm{mod}\: p\right)\\ & &\equiv (-1)^n r_1\cdot r_2\cdots r_m\cdot s_1\cdot s_2\cdots s_n \:\left(\mathrm{mod}\: p\right)\\ & &\equiv (-1)^n a\cdot 2a\cdot 3a\cdots\frac{p-1}{2}a \:\left(\mathrm{mod}\: p\right)\\ & &\equiv (-1)^n a^{\frac{p-1}{2}} \left(\frac{p-1}{2}\right)! \:\left(\mathrm{mod}\: p\right). \end{eqnarray*} \] Since \(\gcd\left(\left(\frac{p-1}{2}\right)!,p\right)=1\), canceling \(\left(\frac{p-1}{2}\right)!\) from both sides we get \[ 1\equiv (-1)^n a^{\frac{p-1}{2}} \:\left(\mathrm{mod}\:p \right).\] Multiplying both sides by \((-1)^n\), we get \[ a^{\frac{p-1}{2}} \equiv (-1)^n \:\left(\mathrm{mod}\: p \right).\] Finally by Euler's criterion we have \[\displaystyle\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \equiv (-1)^n \:\left(\mathrm{mod}\: p \right). ◼ \]

Proof. For each \(k=1,2,\ldots,(p-1)/2\), applying Division Theorem on \(ka\) and \(p\) we get unique positive integer \(t_k < p\) for which \[ ka=\left\lfloor \frac{ka}{p}\right\rfloor p+ t_k.\] Let \(r_1,r_2,\ldots,r_m,s_1,s_2,\ldots,s_n\) be the least positive residues of integers in \(S\) modulo \(p\) where \(m+n=(p-1)/2\) and \[ r_1< r_2<\cdots< r_m<\frac{p}{2}< s_1< s_2<\cdots< s_n.\] Note that \[\{r_1,r_2,\ldots,r_m,s_1,s_2,\ldots,s_n\}=\{t_1,t_2,\ldots,t_{(p-1)/2}\}.\] Then \[ \begin{equation} \sum_{k=1}^{(p-1)/2} ka=\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p} \right\rfloor p+\sum_{k=1}^{(p-1)/2} t_k=p\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p}\right\rfloor + \sum_{k=1}^{m}r_k +\sum_{k=1}^{n} s_k \:\:\:(1) \end{equation}\] By the proof of Gauss's Lemma, \[\left\lbrace r_1,r_2,\ldots,r_m,p-s_1,p-s_2,\ldots,p-s_n \right\rbrace=\left\lbrace 1,2,3,\ldots,\frac{p-1}{2} \right\rbrace.\] Then \[ \begin{equation} \sum_{k=1}^{(p-1)/2} k= \sum_{k=1}^{m}r_k +\sum_{k=1}^{n} (p-s_k)= pn+ \sum_{k=1}^{m}r_k -\sum_{k=1}^{n} s_k \:\:\:(2) \end{equation}\] Subtracting (2) from (1) we get \[ \begin{eqnarray} (a-1)\sum_{k=1}^{(p-1)/2} k &=&-pn+p \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p}\right\rfloor + 2 \sum_{k=1}^{n} s_k \nonumber\\ p\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p}\right\rfloor &=& pn+(a-1)\displaystyle\sum_{k=1}^{(p-1)/2} k-2 \sum_{k=1}^{n} s_k. \:\:\:(3) \end{eqnarray} \] Since \(a\) is odd, \(a-1\equiv 0 \:\left(\mathrm{mod}\:2\right) \). Thus from (3) we get \[ p\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p} \right\rfloor = pn+(a-1)\displaystyle\sum_{k=1}^{(p-1)/2} k-2 \sum_{k=1}^{n} s_k \equiv pn+0+0 \:\left(\mathrm{mod}\: 2\right).\] Since \(p\) is odd, \(\gcd(p,2)=1\). By canceling \(p\) from both sides, we get \[ n\equiv \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p} \right\rfloor \:\left(\mathrm{mod}\: 2\right).\] Finally by Gauss's Lemma, \[\displaystyle\left(\frac{a}{p}\right)=(-1)^n=(-1)^{\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{ka}{p} \right\rfloor}. ◼ \]

Proof. First we combinatorially prove that \[\frac{p-1}{2}\frac{q-1}{2}=\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor +\sum_{k=1}^{(q-1)/2} \left\lfloor \frac{kp}{q} \right\rfloor.\]

Consider the following open rectangular region \[ R=\{(x,y)\;|\; 0< x < p/2,\; 0< y < q/2 \}.\] The number of lattice points in \(R\) is \(\frac{p-1}{2}\times\frac{q-1}{2}.\) Now we show that none of the lattice points of \(R\) lies on the line \(y=\frac{q}{p}x\). Consider a lattice point \((a,b)\) on \(y=\frac{q}{p}x\). Then \(b=\frac{q}{p}a\), i.e., \(bp=aq\). So \(p\vert aq\). Since \(p\nmid q\), \(p\vert a\). By construction \(R\) has no lattice points \((a,b)\) where \(a\) is a multiple of \(p\). Thus \((a,b)\notin R\).

Consider the two open triangular regions inside \(R\) below and above the line \(y=\frac{q}{p}x\): \[ T_L=\{ (x,y)\;|\; 0< x < p/2,\; 0< y < \frac{q}{p}x\} \text{ and } \] \[ T_U=\{ (x,y)\;|\; 0< x < p/2,\; \frac{q}{p}x < y < q/2 \}. \] Note that the sum of numbers of lattice points in \(T_L\) and \(T_R\) is \(\frac{p-1}{2}\frac{q-1}{2}\), the number of lattice points in \(R\). Let us count the number of lattice points in \(T_L\) and \(T_R\).

Suppose \((k,l)\) is a lattice point in \(T_L\). Then \(1\leq k\leq (p-1)/2\). If \((k,l)\) is on the vertical line through \((k,0)\), then \(1\leq l\leq \left\lfloor \frac{q}{p}k \right\rfloor \). Thus the total number of lattice points in \(T_L\) is \[\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor.\] Similarly the total number of lattice points in \(T_U\) is \[\sum_{k=1}^{(q-1)/2} \left\lfloor \frac{kp}{q} \right\rfloor.\] Thus \[\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor+\sum_{k=1}^{(q-1)/2} \left\lfloor \frac{kp}{q} \right\rfloor =\frac{p-1}{2}\frac{q-1}{2}.\] Now by Eisenstein's Lemma, \[\displaystyle\left(\frac{p}{q} \right) \displaystyle\left(\frac{q}{p}\right)= (-1)^{\scriptstyle\sum_{k=1}^{(q-1)/2} \left\lfloor \frac{kp}{q} \right\rfloor} (-1)^{\scriptstyle\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor} = (-1)^{\scriptstyle\sum_{k=1}^{(q-1)/2} \left\lfloor \frac{kp}{q} \right\rfloor +\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor} = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}. ◼ \]