The law of quadratic reciprocity 27 First proof.The key to our first proof(which is Gauss'third)is a counting formula that soon came to be called the Lemma of Gauss: Lemma of Gauss.Suppose a0(modp).Take the numbers 1a,2a,a and reduce them modulo p to the residue system smallest in absolute vale,ia≡r,(modp)with-2号≤rn≤P号 for all i.Then ()=(-1),where s=#). Proof.Suppose u,...,u are the residues smaller than 0.and that v1,...,are those greater than 0.Then the numbers-u1,...,- are between 1 and,and are all different from the vjs(see the margin); If-ui=vj,then ui+j=0(mod p). hence u1,...v1...={1,2....27).Therefore Nowu≡ka,v≡la(modp)implies p(k+e)a.As p and a are relatively Π-u)Ⅱ%=学， prime,p must divide k+e which is im- possible,since k+e<p-1. which implies (-l)Π“Π三学！(modp. Now remember how we obtained the numbers ui and vj;they are the residues of 1a,a.Hence 1=(-1)°Π4Πy三(-1)°1a学(modp). Cancelling !together with Euler's criterion gives (分=a学三(-modp), and therefore ()=(-1)",since p is odd. 口 With this we can easily compute ()Since 12,2.2,....2 are all between 1 and p-1,we have s=#{i:号<2i≤p-1-号-#{i:2i≤号}-「1. Check that s is even precisely for p=8k+1. The Lemma of Gauss is the basis for many of the published proofs of the quadratic reciprocity law.The most elegant may be the one suggested by Ferdinand Gotthold Eisenstein,who had learned number theory from Gauss'famous Disquisitiones Arithmeticae and made important contribu- tions to"higher reciprocity theorems"before his premature death at age 29. His proof is just counting lattice points!
The law of quadratic reciprocity 27 First proof. The key to our first proof (which is Gauss’ third) is a counting formula that soon came to be called the Lemma of Gauss: Lemma of Gauss. Suppose a ≡ 0 (mod p). Take the numbers 1a, 2a, . . . , p−1 2 a and reduce them modulo p to the residue system smallest in absolute value, ia ≡ ri (mod p) with −p−1 2 ≤ ri ≤ p−1 2 for all i. Then ( a p )=(−1)s, where s = #{i : ri < 0}. Proof. Suppose u1,...,us are the residues smaller than 0, and that v1,...,v p−1 2 −s are those greater than 0. Then the numbers −u1,..., −us are between 1 and p−1 2 , and are all different from the vj s (see the margin); hence {−u1,..., −us, v1,...,v p−1 2 −s} = {1, 2,..., p−1 2 }. Therefore If −ui = vj , then ui + vj ≡ 0 (mod p). Now ui ≡ ka, vj ≡ a (mod p) implies p|(k + )a. As p and a are relatively prime, p must divide k + which is impossible, since k + ≤ p − 1. i (−ui) j vj = p−1 2 !, which implies (−1)s i ui j vj ≡ p−1 2 ! (mod p). Now remember how we obtained the numbers ui and vj ; they are the residues of 1a, ··· , p−1 2 a. Hence p−1 2 ! ≡ (−1)s i ui j vj ≡ (−1)s p−1 2 ! a p−1 2 (mod p). Cancelling p−1 2 ! together with Euler’s criterion gives ( a p ) ≡ a p−1 2 ≡ (−1)s (mod p), and therefore ( a p )=(−1)s, since p is odd. With this we can easily compute ( 2 p ): Since 1 · 2, 2 · 2,..., p−1 2 · 2 are all between 1 and p − 1, we have s = #{i : p−1 2 < 2i ≤ p − 1} = p−1 2 − #{i : 2i ≤ p−1 2 } = p−1 4 . Check that s is even precisely for p = 8k ± 1. The Lemma of Gauss is the basis for many of the published proofs of the quadratic reciprocity law. The most elegant may be the one suggested by Ferdinand Gotthold Eisenstein, who had learned number theory from Gauss’ famous Disquisitiones Arithmeticae and made important contributions to “higher reciprocity theorems” before his premature death at age 29. His proof is just counting lattice points!
28 The law of quadratic reciprocity Let p and g be odd primes,and consider ()Suppose ig is a multiple of g that reduces to a negative residue ri<0 in the Lemma of Gauss.This means that there is a unique integer j such that-2<ig-jp <0.Note that 0<j<since 0<i<B.In other words,()=(-1)",where s is the number of lattice points(,y),that is,pairs of integers y satisfying 0<m-9r<号0<工<号0<y<是 (3) Similarly.()=(-1)wheret is the number of lattice points(,y)with 0<qr-四<号0<r<号0<y<号 (4) Now look at the rectangle with side lengths号，号，and draw the two lines parallel to the diagonal py=gr.y=+or py-gx=2,respectively, y=(x-)orgx-py=是 The figure shows the situation for p=17,g=11. 11 2 p=17q=11 R s=5t=3 (9)=(1°=-1 份=(-103=-1 The proof is now quickly completed by the following three observations: 1.There are no lattice points on the diagonal and the two parallels.This is so because py gx would imply plx,which cannot be.For the parallels observe that py-gx is an integer whileB and 3 are not. 2.The lattice points observing(3)are precisely the points in the upper strip 0<py -qx <B,and those of (4)the points in the lower strip 0<gx-py 3.Hence the number of lattice points in the two strips is s+t. 3.The outer regions R:py -gx and S:qx -py >contain the same number of points.To see this consider the map:RS which maps (y)to (-,1-y)and check that is an involution. Since the total number of lattice points in the rectangle is,we infer that s+t andhave the same parity,and so 月)=(-)*=(-1)学 口
28 The law of quadratic reciprocity Let p and q be odd primes, and consider ( q p ). Suppose iq is a multiple of q that reduces to a negative residue ri < 0 in the Lemma of Gauss. This means that there is a unique integer j such that −p 2 < iq − jp < 0. Note that 0 <j< q 2 since 0 <i< p 2 . In other words, ( q p )=(−1)s, where s is the number of lattice points (x, y), that is, pairs of integers x, y satisfying 0 < py − qx < p 2 , 0 <x< p 2 , 0 <y< q 2 . (3) Similarly, ( p q )=(−1)t where t is the number of lattice points (x, y) with 0 < qx − py < q 2 , 0 <x< p 2 , 0 <y< q 2 . (4) Now look at the rectangle with side lengths p 2 , q 2 , and draw the two lines parallel to the diagonal py = qx, y = q p x+ 1 2 or py −qx = p 2 , respectively, y = q p (x − 1 2 ) or qx − py = q 2 . The figure shows the situation for p = 17, q = 11. R S 17 2 11 2 p = 17 q = 11 s = 5 t = 3 q p = (−1)5 = −1 p q = (−1)3 = −1 The proof is now quickly completed by the following three observations: 1. There are no lattice points on the diagonal and the two parallels. This is so because py = qx would imply p|x, which cannot be. For the parallels observe that py − qx is an integer while p 2 and q 2 are not. 2. The lattice points observing (3) are precisely the points in the upper strip 0 < py − qx < p 2 , and those of (4) the points in the lower strip 0 < qx − py < q 2 . Hence the number of lattice points in the two strips is s + t. 3. The outer regions R : py − qx > p 2 and S : qx − py > q 2 contain the same number of points. To see this consider the map ϕ : R → S which maps (x, y) to ( p+1 2 − x, q+1 2 − y) and check that ϕ is an involution. Since the total number of lattice points in the rectangle is p−1 2 · q−1 2 , we infer that s + t and p−1 2 · q−1 2 have the same parity, and so q p p q = (−1)s+t = (−1) p−1 2 q−1 2 .
The law of quadratic reciprocity 29 Second proof.Our second choice does not use Gauss'lemma,instead it employs so-called "Gauss sums"in finite fields.Gauss invented them in his study of the equation P-1=0 and the arithmetical properties of the field Q()(called cyclotomic field),where is a p-th root of unity.They have been the starting point for the search for higher reciprocity laws in general number fields. Let us first collect a few facts about finite fields. A.Let p and g be different odd primes,and consider the finite field F with gP-1 elements.Its prime field is Za.whence ga =0 for any a E F.This implies that (a+b)=a+b9,since any binomial coefficient()is a multiple of g for 0<i<g.and thus 0 in F.Note that Euler's criterion is an equation (p in the prime field B.The multiplicative group F=F{0}is cyclic of size q-1-1 (see the box on the next page).Since by Fermat's little theorem p is a divisor of gP-1-1,there exists an element F of order p,that is, CP 1,and generates the subgroup {s2,...,p 1}of F*.Note that any (i p)is again a generator.Hence we obtain the polynomial decomposition xP-1 =(x-s)(x-2)...(r -(P). Now we can go to work.Consider the Gauss sum where()is the Legendre symbol.For the proof we derive two different expressions for Ga and then set them equal. First expression.We have G9= 2-x”-月2x”-a。 Example:Take p 3,g 5.Then G=(-2andG5=c5-(10=2-( where the first equality follows from (a +b)9=a9+b9,the second uses =-(-2)=-G,corresponding to that ()=()since g is odd,the third one is derived from (2),which ()=()=-1. yields ()=()()and the last one holds since ig runs with i through all nonzero residues modulo p. Second expression.Suppose we can prove G2=(-1)号p, (6) then we are quickly done.Indeed, G9=G(G2)学=G(-1)学号p号=G)(-1)学号. (7) Equating the expressions in(5)and (7)and cancelling G,which is nonzero by(6,we find(g)=()(-l)学学，and thus 月=←1)学学
The law of quadratic reciprocity 29 Second proof. Our second choice does not use Gauss’ lemma, instead it employs so-called “Gauss sums” in finite fields. Gauss invented them in his study of the equation xp −1=0 and the arithmetical properties of the field Q(ζ) (called cyclotomic field), where ζ is a p-th root of unity. They have been the starting point for the search for higher reciprocity laws in general number fields. Let us first collect a few facts about finite fields. A. Let p and q be different odd primes, and consider the finite field F with qp−1 elements. Its prime field is Zq , whence qa = 0 for any a ∈ F. This implies that (a + b)q = aq + bq, since any binomial coefficient q i is a multiple of q for 0 <i<q, and thus 0 in F. Note that Euler’s criterion is an equation ( p q ) = p q−1 2 in the prime field Zq. B. The multiplicative group F∗ = F \ {0} is cyclic of size qp−1 − 1 (see the box on the next page). Since by Fermat’s little theorem p is a divisor of qp−1 − 1, there exists an element ζ ∈ F of order p, that is, ζp = 1, and ζ generates the subgroup {ζ,ζ2,...,ζp = 1} of F∗. Note that any ζi (i = p) is again a generator. Hence we obtain the polynomial decomposition xp − 1=(x − ζ)(x − ζ2)···(x − ζp). Now we can go to work. Consider the Gauss sum G := p −1 i=1 i p ζi ∈ F, where ( i p ) is the Legendre symbol. For the proof we derive two different expressions for Gq and then set them equal. First expression. We have Example: Take p = 3, q = 5. Then G = ζ−ζ2 and G5 = ζ5−ζ10 = ζ2−ζ = −(ζ − ζ2) = −G, corresponding to ( 5 3 )=( 2 3 ) = −1. Gq = p −1 i=1 ( i p ) qζiq = p −1 i=1 ( i p )ζiq = ( q p ) p −1 i=1 ( iq p )ζiq = ( q p )G, (5) where the first equality follows from (a + b)q = aq + bq, the second uses that ( i p )q = ( i p ) since q is odd, the third one is derived from (2), which yields ( i p )=( q p )( iq p ), and the last one holds since iq runs with i through all nonzero residues modulo p. Second expression. Suppose we can prove G2 = (−1) p−1 2 p , (6) then we are quickly done. Indeed, Gq = G(G2) q−1 2 = G(−1) p−1 2 q−1 2 p q−1 2 = G( p q )(−1) p−1 2 q−1 2 . (7) Equating the expressions in (5) and (7) and cancelling G, which is nonzero by (6), we find ( q p )=( p q )(−1) p−1 2 q−1 2 , and thus ( q p )(p q )=(−1) p−1 2 q−1 2
30 The law of quadratic reciprocity The multiplicative group of a finite field is cyclic Let F*be the multiplicative group of the field F,with F=n. Writing ord(a)for the order of an element,that is,the smallest pos- itive integer k such that ak=1,we want to find an element a F* with ord(a)=n.If ord(b)=d,then by Lagrange's theorem,d divides n(see the margin on page 4).Classifying the elements ac- cording to their order,we have n=>v(d),where (d)=#F:ord(b)=d}.(8) dn Iford(b)=d.then every element bi (i=1,...,d)satisfies(b)d=1 and is therefore a root of the polynomial rd-1.But,since F is a field,zd-1 has at most d roots,and so the elements b,b2,...,b =1 are precisely these roots.In particular,every element of order d is of the form b'. On the other hand,it is easily checked that ord()where (i,d)denotes the greatest common divisor of i and d.Hence ord(bi)=d if and only if (i,d)=1,that is,if i and d are rela- tively prime.Denoting Euler's function by (d)=#fi:1 <i< d,(i,d)=1,we thus have (d)=o(d)whenever (d)>0. Looking at (8)we find n=∑(d≤∑（④. dn dn But,as we are going to show that ∑个=n, (9) d| we must have (d)=(d)for all d.In particular,(n)=(n)>1, and so there is an element of order n. The following(folklore)proof of(9)belongs in the Book as well. “Even in total chaos Consider the n fractions we can hang on to the cyclic group" 品品奈…，升 reduce them to lowest terms÷=音with 1≤i≤d,(i,d=l,dln, and check that the denominator d appears precisely (d)times. It remains to verify(6),and for this we first make two simple observations: ·∑=1-0 and thus∑==-l.Just note that-∑1 is the coefficient of x-1 in P-1=(-),and thus 0. ·∑Rai(匀)=0 and thus∑R=(台)=-（月），since there are equally many quadratic residues and nonresidues
30 The law of quadratic reciprocity The multiplicative group of a finite field is cyclic Let F∗ be the multiplicative group of the field F, with |F∗| = n. Writing ord(a) for the order of an element, that is, the smallest positive integer k such that ak = 1, we want to find an element a ∈ F∗ with ord(a) = n. If ord(b) = d, then by Lagrange’s theorem, d divides n (see the margin on page 4). Classifying the elements according to their order, we have n = d| n ψ(d), where ψ(d)=#{b ∈ F∗ : ord(b) = d}. (8) If ord(b) = d, then every element bi (i = 1,...,d) satisfies (bi )d = 1 and is therefore a root of the polynomial xd − 1. But, since F is a field, xd−1 has at most d roots, and so the elements b, b2,...,bd = 1 are precisely these roots. In particular, every element of order d is of the form bi . On the other hand, it is easily checked that ord(bi ) = d (i,d) , where (i, d) denotes the greatest common divisor of i and d. Hence ord(bi ) = d if and only if (i, d)=1, that is, if i and d are relatively prime. Denoting Euler’s function by ϕ(d)=#{i : 1 ≤ i ≤ d,(i, d)=1}, we thus have ψ(d) = ϕ(d) whenever ψ(d) > 0. Looking at (8) we find n = d| n ψ(d) ≤ d| n ϕ(d). But, as we are going to show that d| n ϕ(d) = n, (9) we must have ψ(d) = ϕ(d) for all d. In particular, ψ(n) = ϕ(n) ≥ 1, and so there is an element of order n. The following (folklore) proof of (9) belongs in the Book as well. Consider the n fractions 1 n , 2 n ,..., k n ,..., n n , reduce them to lowest terms k n = i d with 1 ≤ i ≤ d, (i, d)=1, d|n, and check that the denominator d appears precisely ϕ(d) times. “Even in total chaos we can hang on to the cyclic group” It remains to verify (6), and for this we first make two simple observations: • p i=1 ζi = 0 and thus p−1 i=1 ζi = −1. Just note that − p i=1 ζi is the coefficient of xp−1 in xp − 1 = p i=1(x − ζi ), and thus 0. • p−1 k=1( k p )=0 and thus p−2 k=1( k p ) = −( −1 p ), since there are equally many quadratic residues and nonresidues
The law of quadratic reciprocity 31 We have c=(日9（月）=∑曾) Settingj=ik (modp)we find =白w-白 For k=p-1=-1(modp)this gives ()(p-1),since (+k=1.Move k =p-1 in front and write c=号0-)+2白3 (1+)i Euler'scriterion:(号)=(-l)学 Since C+k is a generator of the group forkp-1,the inner sum equals -1for allp-1by our first observation.Hence the second summand is-∑R=i(台)=（分）by our second observation.1 follows Forp=3.g=5.G&2=(《-(2y= that G2=()p and thus with Euler's criterion G2 =(-1)p,which 2-23+4=2-2+5=-3= 3-1 completes the proof. (-1)3，since1+(+2=0. References [1]A.BAKER:A Concise Introduction to the Theory of Numbers,Cambridge Uni- versity Press,Cambridge 1984. [2]F.G.EISENSTEIN:Geometrischer Beweis des Fundamentaltheorems fir die quadratischen Reste,J.Reine Angewandte Mathematik 28(1844),186-191. [3]C.F.GAUSS:Theorema arithmetici demonstratio nova,Comment.Soc.regiae sci.Gottingen XVI (1808),69;Werke II,1-8 (contains the 3rd proof). [4]C.F.GAUSS:Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplicationes novae (1818),Werke II,47-64 (contains the 6th proof). [5]F.LEMMERMEYER:Reciprocity Laws,Springer-Verlag,Berlin 2000
The law of quadratic reciprocity 31 We have G2 = p−1 i=1 i p ζi p −1 j=1 j p ζj = i,j ij p ζi+j . Setting j ≡ ik (mod p) we find G2 = i,k k p ζi(1+k) = p −1 k=1 k p p −1 i=1 ζ(1+k)i . For k = p−1 ≡ −1 (mod p) this gives ( −1 p )(p−1), since ζ1+k = 1. Move k = p − 1 in front and write Euler’s criterion: ( −1 p )=(−1) p−1 G2 = 2 −1 p (p − 1) +p−2 k=1 k p p −1 i=1 ζ(1+k)i . Since ζ1+k is a generator of the group for k = p − 1, the inner sum equals p−1 i=1 ζi = −1 for all k = p−1 by our first observation. Hence the second summand is − p−2 k=1( k p )=( −1 p ) by our second observation. It follows that G2 = ( −1 p )p and thus with Euler’s criterion G2 = (−1) p−1 2 p, which For p = 3, q = 5, G2 = (ζ − ζ2) 2 = ζ2 − 2ζ3 + ζ4 = ζ2 − 2 + ζ = −3 = (−1) 3−1 2 3, since 1 + ζ + ζ2 completes the proof. = 0. References [1] A. BAKER: A Concise Introduction to the Theory of Numbers, Cambridge University Press, Cambridge 1984. [2] F. G. EISENSTEIN: Geometrischer Beweis des Fundamentaltheorems für die quadratischen Reste, J. Reine Angewandte Mathematik 28 (1844), 186-191. [3] C. F. GAUSS: Theorema arithmetici demonstratio nova, Comment. Soc. regiae sci. Göttingen XVI (1808), 69; Werke II, 1-8 (contains the 3rd proof). [4] C. F. GAUSS: Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplicationes novae (1818), Werke II, 47-64 (contains the 6th proof). [5] F. LEMMERMEYER: Reciprocity Laws, Springer-Verlag, Berlin 2000.