mersenneforum.org > Math Basic Number Theory 17: quadratic reciprocity
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-31, 14:41 #1 Nick     Dec 2012 The Netherlands 101110111102 Posts Basic Number Theory 17: quadratic reciprocity Which numbers are squares? More precisely, for which $$a$$ does there exist $$x$$ with $$x^2=a$$? The answer depends on which number system we work in, of course. In the real numbers, if $$a\geq 0$$ then $$a$$ is a square (put $$x=\sqrt{a}$$), while if $$a<0$$ then it is not a square (since $$x^2\geq 0$$ for all real $$x$$), so the squares are precisely the non-negative numbers. It follows, for any real numbers $$x,y$$, that if $$x$$ is not a square and $$y$$ is not a square then their product $$xy$$ is a square. This is a pattern that we shall see again shortly. Let $$n$$ be a positive integer. An integer $$a$$ is called a quadratic residue modulo $$n$$ if there exists an integer $$x$$ such that $$x^2\equiv a\pmod{n}$$ (or, equivalently, if $$\bar{a}$$ is a square in $$\mathbb{Z}/n\mathbb{Z}$$). As ever in modular arithmetic, the key is to understand what happens modulo the prime numbers. And every integer is a quadratic residue modulo 2, so we focus on odd primes. Let $$p$$ be an odd prime number. For each integer $$a$$, we define the Legendre symbol $$(\frac{a}{p})$$ as follows: if $$p$$ divides $$a$$ then $$(\frac{a}{p})=0$$. If $$p$$ does not divide $$a$$ then $$(\frac{a}{p})=1$$ if $$a$$ is a quadratic residue modulo $$p$$, and -1 otherwise. For example, $$(\frac{-15}{5})=0$$, $$(\frac{19}{5})=1$$ and $$(\frac{3}{5})=-1$$. Proposition 99 Let $$p$$ be an odd prime number. Then, for all integers $$a$$, $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}.$ proof Take any integer $$a$$. If $$p|a$$ then $$(\frac{a}{p})=0\equiv a^{\frac{p-1}{2}}\pmod{p}$$. Suppose $$p$$ does not divide $$a$$. Then (by corollary 40) $$a^{p-1}\equiv 1\pmod{p}$$ so (by proposition 60) $$a^{\frac{p-1}{2}}\equiv 1\pmod{p}$$ or $$a^{\frac{p-1}{2}}\equiv -1\pmod{p}$$. Now the unit group of the integers modulo $$p$$ is cyclic (by theorem 90) so there exists an integer $$g$$ such that $\left(\mathbb{Z}/p\mathbb{Z}\right)^*=\{\bar{1},\bar{g},\bar{g}^2,\bar{g}^3, \ldots,\bar{g}^{p-2}\}$ with $$\bar{g}^{p-1}=\bar{1}$$. Let $$H=\{\bar{g}^{2n}:n\in\mathbb{Z}\}$$, the set of all squares in $$(\mathbb{Z}/p\mathbb{Z})^*$$. Then $$H$$ is the cyclic subgroup generated by $$\bar{g}^2$$ and, by proposition 86, $$H$$ has precisely $$\frac{p-1}{2}$$ elements, i.e. $H=\{\bar{1},\bar{g}^2,\bar{g}^4,\bar{g}^6,\ldots,\bar{g}^{p-3}\}.$ As $$p$$ does not divide $$a$$, $$\bar{a}$$ is an element of $$(\mathbb{Z}/p\mathbb{Z})^*$$, so $$\bar{a}=\bar{g}^r$$ for some $$r\in\{0,1,\ldots,p-2\}$$. If $$(\frac{a}{p})=1$$ then $$\bar{a}\in H$$ so $$r$$ is even, i.e. $$r=2s$$ for some integer $$s$$, and therefore $$\bar{a}^{\frac{p-1}{2}}=\bar{g}^{s(p-1)}=\bar{1}$$ giving $$a^{\frac{p-1}{2}}\equiv 1\pmod{p}$$. Conversely, if $$a^{\frac{p-1}{2}}\equiv 1\pmod{p}$$ then $$\bar{g}^{\frac{r(p-1)}{2}}=\bar{1}$$ and $$\bar{g}$$ has order $$p-1$$ so, by proposition 75, $$p-1$$ divides $$\frac{r(p-1)}{2}$$. Thus $$r$$ is even and $$\bar{a}=\bar{g}^r\in H$$, hence $$(\frac{a}{p})=1$$. ∎ Corollary 100 Let $$p$$ be an odd prime number. Then, for all integers $$a,b$$, $$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$$. proof For any integers $$a,b$$, proposition 99 gives $\left(\frac{ab}{p}\right)\equiv (ab)^{\frac{p-1}{2}} =a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)\pmod{p}$ hence $$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$$. ∎ In particular, for any odd prime number $$p$$ and integers $$a,b$$, if $$a$$ is not a square modulo $$p$$ and $$b$$ is not a square modulo $$p$$ then their product $$ab$$ is a square modulo $$p$$ (just as with real numbers). Recall that, for any integer $$a$$ and positive integer $$n$$, we write $$a\bmod{n}$$ for the remainder on dividing $$a$$ by $$n$$, which is an integer in the range 0 to $$n-1$$ inclusive. Proposition 101 Let $$p$$ be an odd prime number and $$a$$ an integer not divisible by $$p$$. Define $$A=\{a,2a,3a,\ldots,\frac{p-1}{2}a\}$$ and $$r=\#\{x\in A:x\bmod{p}>\frac{p}{2}\}$$. Then $$(\frac{a}{p})=(-1)^r$$. proof Each element of the set $$A$$ is congruent (modulo $$p$$) with a unique integer between $$-\frac{p}{2}$$ and $$\frac{p}{2}$$, and no element of $$A$$ is congruent with 0 (modulo $$p$$) so all these integers are positive or negative. Let $$r_1,r_2,\ldots,r_k$$ be the positive ones and $$-s_1,-s_2,\ldots,-s_m$$ the negative ones. (Thus $$k,m$$ are non-negative integers with $$k+m=\frac{p-1}{2}$$ and, for each $$i\in\{1,2,\ldots,k\}$$ and each $$j\in\{1,2,\ldots,m\}$$ we have $$02$$) so $$(\frac{a}{p})=(-1)^r$$. ∎ Example For which odd prime numbers $$p$$ is 2 a square modulo $$p$$? Let $$A=\{2,4,6,\ldots,p-1\}$$. In this case, all elements of $$A$$ are less than $$p$$, so we simply need to count how many of them are greater than $$\frac{p}{2}$$. If $$p\equiv 1\pmod{4}$$ then the elements of $$A$$ greater than $$\frac{p}{2}$$ are $$\{\frac{p+3}{2},\frac{p+7}{2},\ldots,p-1\}$$. There are $$\frac{p-1}{4}$$ elements here, so $$(\frac{2}{p})=(-1)^{\frac{p-1}{4}}$$ which is 1 if and only if $$p\equiv 1\pmod{8}$$. If instead $$p\equiv 3\pmod{4}$$ then the elements of $$A$$ greater than $$\frac{p}{2}$$ are $$\{\frac{p+1}{2},\frac{p+5}{2},\ldots,p-1\}$$. There are $$\frac{p+1}{4}$$ elements here, so $$(\frac{2}{p})=(-1)^{\frac{p+1}{4}}$$ which is 1 if and only if $$p\equiv -1\pmod{8}$$. Conclusion: for any odd prime number $$p$$, 2 is a quadratic residue modulo $$p$$ if and only if $$p\equiv\pm 1\pmod{8}$$. For distinct odd prime numbers $$p,q$$, we can consider whether $$p$$ is a quadratic residue modulo $$q$$ and also whether $$q$$ is a quadratic residue modulo $$p$$ and, at first sight, there is no reason why these two questions should be related. It is one of the gems of Number Theory that there is a simple relationship between them. Before we can prove this, we need a small lemma. Lemma 102 Let $$p,q$$ be odd positive integers, $$A=\{1,2,\ldots,\frac{p-1}{2}\}$$, and $$B=\{1,2,\ldots,\frac{q-1}{2}\}$$. Define $$U=\{(a,b)\in A\times B:aq-bp<-\frac{p}{2}\}$$ and $$W=\{(a,b)\in A\times B:aq-bp>\frac{q}{2}\}$$. Then $$\#U=\#W$$. proof Let $$f:A\rightarrow A$$ be the function $$a\mapsto \frac{p+1}{2}-a$$ and $$g:B\rightarrow B$$ be the function $$b\mapsto \frac{q+1}{2}-b$$. Then $$f,g$$ are each bijective with $$f^{-1}=f$$ and $$g^{-1}=g$$. Take any $$a\in A$$ and any $$b\in B$$. Then $f(a)q-g(b)p =\left(\frac{p+1}{2}-a\right)q-\left(\frac{q+1}{2}-b\right)p =\frac{q}{2}-\frac{p}{2}-(aq-bp).$ If $$(a,b)\in U$$ then $$aq-bp<-\frac{p}{2}$$ so $$\frac{q}{2}-\frac{p}{2}-(aq-bp)>\frac{q}{2}$$ and therefore $$(f(a),g(b))\in W$$. Conversely, if $$(a,b)\in W$$ then $$aq-bp>\frac{q}{2}$$ so $$\frac{q}{2}-\frac{p}{2}-(aq-bp)<-\frac{p}{2}$$ and therefore $$(f^{-1}(a),g^{-1}(b))=(f(a),g(b))\in U$$. Hence the function $$h:U\rightarrow W$$ given by $$(a,b)\mapsto (f(a),g(b))$$ is bijective and it follows that $$\#U=\#W$$. ∎ Theorem 103 Let $$p,q$$ be distinct odd prime numbers. Then $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) =\left(-1\right)^{\frac{(p-1)(q-1)}{4}}.$ proof Let $$A=\{1,2,\ldots,\frac{p-1}{2}\}$$ and $$B=\{1,2,\ldots,\frac{q-1}{2}\}$$. For each $$a\in A$$, there exist unique integers $$b,r$$ such that $$aq=bp+r$$ and $$0\leq r\frac{p}{2}$$. Then $$(\frac{q}{p})=(-1)^s$$ by proposition 101. Instead of taking the remainder $$r$$ in the range 0 to $$p-1$$ inclusive, we may take it in the range $$-\frac{p-1}{2}$$ to $$\frac{p-1}{2}$$ inclusive, and then $$s$$ is the number of $$a\in A$$ for which we get $$r<0$$. As the quotient $$b$$ is unique in each case, we also have $$s=\#S$$ where $$S=\{(a,b)\in\mathbb{Z}^2:a\in A,-\frac{p}{2}aq$$ with $$p,a,q$$ all positive so $$b>0$$ (and $$b$$ is an integer) hence $$b\geq 1$$. Also $$bp\frac{q}{2}\right\} \end{eqnarray*}\] Then the sets \(U,V,W$$ form a partition of $$A\times B$$ so $$\#(A\times B)=\#U+\#V+\#W$$. For any $$a\in A$$ and any $$b\in B$$, $$p$$ does not divide $$a$$ and the primes $$p,q$$ are distinct so $$aq-bp\neq 0$$. Thus $$\#V=\#S+\#T=s+t$$. And by lemma 102 we have $$\#U=\#W$$ so $s+t=\#V\equiv\#(A\times B)=\frac{p-1}{2}\cdot\frac{q-1}{2}\pmod{2}$ hence $$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)=(-1)^{s+t}=\left(-1\right)^{\frac{(p-1)(q-1)}{4}}$$. ∎ Corollary 104 Quadratic Reciprocity Let $$p,q$$ be distinct odd prime numbers. If $$p\equiv 1\pmod{4}$$ or $$q\equiv 1\pmod{4}$$ (or both) then $$(\frac{q}{p})=(\frac{p}{q})$$, and otherwise $$(\frac{q}{p})=-(\frac{p}{q})$$. proof If $$p\equiv 1\pmod{4}$$ or $$q\equiv 1\pmod{4}$$ then $$\frac{(p-1)(q-1)}{4}$$ is even so, by theorem 103, $$(\frac{p}{q})(\frac{q}{p})=1$$ and therefore $$(\frac{q}{p})=(\frac{p}{q})$$. If instead $$p\equiv q\equiv 3\pmod{4}$$ then $$\frac{(p-1)(q-1)}{4}$$ is odd so, by theorem 103, $$(\frac{p}{q})(\frac{q}{p})=-1$$ and therefore $$(\frac{q}{p})=-(\frac{p}{q})$$. ∎ Example Is 87 a square modulo 127? Using corollary 100 and corollary 104, we see that $\begin{eqnarray*} \left(\frac{87}{127}\right) & = & \left(\frac{3}{127}\right) \left(\frac{29}{127}\right) = -\left(\frac{127}{3}\right) \left(\frac{29}{127}\right) \\ & = & -\left(\frac{1}{3}\right) \left(\frac{29}{127}\right) = -\left(\frac{29}{127}\right) = -\left(\frac{127}{29}\right) \\ & = & -\left(\frac{11}{29}\right) = -\left(\frac{29}{11}\right) = -\left(\frac{7}{11}\right) \\ & = & \left(\frac{11}{7}\right) = \left(\frac{4}{7}\right)=1 \end{eqnarray*}$ so 87 is a square modulo 127. Exercises 79. Is 65 a quadratic residue modulo 31? 80. For which odd prime numbers $$p$$ is -2 a square modulo $$p$$? 81. Find all integers $$x$$ such that $$x^2\equiv 1\pmod{12}$$. 82. Let $$z$$ be a complex number such that $$z^8=1$$ but $$z^4\neq 1$$. Show that $$z+z^{-1}=\pm\sqrt{2}$$. Last fiddled with by Nick on 2017-08-18 at 17:17 Reason: Typo (found by wreck - thank you!)

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2017-12-23 20:10 Nick Number Theory Discussion Group 5 2017-04-25 14:32 Nick Number Theory Discussion Group 4 2017-03-27 06:01 Nick Number Theory Discussion Group 0 2016-12-29 13:47 Nick Number Theory Discussion Group 5 2016-10-08 09:05

All times are UTC. The time now is 17:54.

Sat Nov 28 17:54:25 UTC 2020 up 79 days, 15:05, 3 users, load averages: 1.09, 1.10, 1.25