22 Representing numbers as sums of two squares Proof.We study the set S={(z,,z)∈Z3:4xy+z2=p,x>0,y>0} This set is finite.ndeed,x≥1 andy≥1 implies y≤2andx≤号.So there are only finitely many possible values for x and y,and given x and y, there are at most two values for z. 1.The first linear involution is given by f:S-→S,(x,y,z)-→(y,x,-2) that is,"interchange x and y,and negate 2."This clearly maps S to itself, and it is an involution:Applied twice,it yields the identity.Also,f has no fixed points,since z=0 would imply p=4xy,which is impossible. Furthermore,f maps the solutions in T={(x,y,z)∈S:z>0} to the solutions in S\T,which satisfy z<0.Also,f reverses the signs of x-y and of z,so it maps the solutions in U={(x,y,z)∈S:(x-y)+z>0} to the solutions in S\U.For this we have to see that there is no solution with(-y)+=0,but there is none since this would give p=4xy+22= 4红y+(红-)2=(z+)2. What do we get from the study of f?The main observation is that since f maps the sets T and U to their complements,it also interchanges the elements in T\U with these in U\T.That is,there is the same number of solutions in U that are not in T as there are solutions in T that are not in U -so T and U have the same cardinality. 2.The second involution that we study is an involution on the set U: g:U-→U,(x,y,z)-→(x-y+z,,2y-2z) First we check that indeed this is a well-defined map:If(,y,2)EU,then -y+>0,>0 and 4(-y+z)y+(2y-z)2=4xy +z2,so g(x,y,z)E S.By (x-y+z)y+(2y-z)=x>0 we find that indeed g(r,y,2)∈U. Also g is an involution:g(,y,z)=(x-y+z,y,2y-z)is mapped by g to(x-y+z)-y+(2y-z),y,2y-(2y-z)=(x,y,z) And finally g has exactly one fixed point: (E,,2）=9(x,,z）=(x-y+2,,2y-z) implies that y=z,but then p=4xy+y2=(4x+y)y,which holds only for y=z=1andx=1. But if g is an involution on U that has exactly one fixed point,then the cardinality of U is odd
22 Representing numbers as sums of two squares Proof. We study the set S := {(x, y, z) ∈ Z3 : 4xy + z2 = p, x > 0, y> 0}. This set is finite. Indeed, x ≥ 1 and y ≥ 1 implies y ≤ p 4 and x ≤ p 4 . So there are only finitely many possible values for x and y, and given x and y, there are at most two values for z. 1. The first linear involution is given by f : S −→ S, (x, y, z) −→ (y, x, −z), that is, “interchange x and y, and negate z.” This clearly maps S to itself, and it is an involution: Applied twice, it yields the identity. Also, f has no fixed points, since z = 0 would imply p = 4xy, which is impossible. Furthermore, f maps the solutions in f U T T := {(x, y, z) ∈ S : z > 0} to the solutions in S\T , which satisfy z < 0. Also, f reverses the signs of x − y and of z, so it maps the solutions in U := {(x, y, z) ∈ S : (x − y) + z > 0} to the solutions in S\U. For this we have to see that there is no solution with (x−y)+z = 0, but there is none since this would give p = 4xy+z2 = 4xy + (x − y)2 = (x + y)2. What do we get from the study of f? The main observation is that since f maps the sets T and U to their complements, it also interchanges the elements in T \U with these in U\T . That is, there is the same number of solutions in U that are not in T as there are solutions in T that are not in U — so T and U have the same cardinality. 2. The second involution that we study is an involution on the set U: g : U −→ U, (x, y, z) −→ (x − y + z, y, 2y − z). First we check that indeed this is a well-defined map: If (x, y, z) ∈ U, then x − y + z > 0,y > 0 and 4(x − y + z)y + (2y − z)2 = 4xy + z2, so g(x, y, z) ∈ S. By (x− y + z)− y + (2y − z) = x > 0 we find that indeed g(x, y, z) ∈ U. Also g is an involution: g(x, y, z)=(x − y + z, y, 2y − z) is mapped by g to ((x − y + z) − y + (2y − z), y, 2y − (2y − z)) = (x, y, z). U g And finally g has exactly one fixed point: (x, y, z) = g(x, y, z)=(x − y + z, y, 2y − z) implies that y = z, but then p = 4xy + y2 = (4x + y)y, which holds only for y = z = 1 and x = p−1 4 . But if g is an involution on U that has exactly one fixed point, then the cardinality of U is odd.
Representing numbers as sums of two squares 23 3.The third,trivial,involution that we study is the involution on T that interchanges x and y: h:T-→T,(x,y,z)-→(y,x,2): This map is clearly well-defined,and an involution.We combine now our knowledge derived from the other two involutions:The cardinality of T is equal to the cardinality of U,which is odd.But if h is an involution on a finite set of odd cardinality,then it has a fixed point:There is a point On a finite set of odd cardinality,every (,y,2)E T withx=y,that is,a solution of involution has at least one fixed point. p=4x2+22=(2x)2+z2 口 Note that this proof yields more-the number of representations of p in the form p=x2+(2y)2 is odd for all primes of the form p=4m+1.(The representation is actually unique,see [3].)Also note that both proofs are not effective:Try to find z and y for a ten digit prime!Efficient ways to find such representations as sums of two squares are discussed in [1]and [7]. The following theorem completely answers the question which started this chapter. Theorem.A natural number n can be represented as a sum of two squares if and only if every prime factor of the form p =4m+3 appears with an even exponent in the prime decomposition of n. Proof.Call a number n representable if it is a sum of two squares,that is,if n =x2+y2 for some z,y E No.The theorem is a consequence of the following five facts. (1)1=12+02 and 2 =12+12 are representable.Every prime of the form p =4m +1 is representable. (2)The product of any two representable numbers n=+and n2= is representable:nin2 =(1z2+y)2+(1y-2y)2. (3)If n is representable,n=x2+y2,then also nz2 is representable,by nz2=(xz)2+(yz)2. Facts (1),(2)and (3)together yield the"if"part of the theorem. (4)If p =4m +3 is a prime that divides a representable number n= z2+y2,then p divides both x and y,and thus p2 divides n.In fact,if we had0(modp),then we could find such that=1(modp), multiply the equation x2+2=0 by 72,and thus obtain 1+22= 1 +(y)2=0(modp),which is impossible for p 4m +3 by Lemma 1. (5)If n is representable,and p 4m +3 divides n,then p2 divides n, and n/p2 is representable.This follows from(4),and completes the proof. 0
Representing numbers as sums of two squares 23 3. The third, trivial, involution that we study is the involution on T that interchanges x and y: h : T −→ T, (x, y, z) −→ (y, x, z). This map is clearly well-defined, and an involution. We combine now our knowledge derived from the other two involutions: The cardinality of T is equal to the cardinality of U, which is odd. But if h is an involution on T h On a finite set of odd cardinality, every involution has at least one fixed point. a finite set of odd cardinality, then it has a fixed point: There is a point (x, y, z) ∈ T with x = y, that is, a solution of p = 4x2 + z2 = (2x) 2 + z2. Note that this proof yields more — the number of representations of p in the form p = x2 + (2y)2 is odd for all primes of the form p = 4m+ 1. (The representation is actually unique, see [3].) Also note that both proofs are not effective: Try to find x and y for a ten digit prime! Efficient ways to find such representations as sums of two squares are discussed in [1] and [7]. The following theorem completely answers the question which started this chapter. Theorem. A natural number n can be represented as a sum of two squares if and only if every prime factor of the form p = 4m + 3 appears with an even exponent in the prime decomposition of n. Proof. Call a number n representable if it is a sum of two squares, that is, if n = x2 + y2 for some x, y ∈ N0. The theorem is a consequence of the following five facts. (1) 1=12 + 02 and 2=12 + 12 are representable. Every prime of the form p = 4m + 1 is representable. (2) The product of any two representable numbers n1 = x2 1 +y2 1 and n2 = x2 2 + y2 2 is representable: n1n2 = (x1x2 + y1y2)2 + (x1y2 − x2y1)2. (3) If n is representable, n = x2 + y2, then also nz2 is representable, by nz2 = (xz)2 + (yz)2. Facts (1), (2) and (3) together yield the “if” part of the theorem. (4) If p = 4m + 3 is a prime that divides a representable number n = x2 + y2, then p divides both x and y, and thus p2 divides n. In fact, if we had x ≡ 0 (mod p), then we could find x such that xx ≡ 1 (mod p), multiply the equation x2 + y2 ≡ 0 by x2, and thus obtain 1 + y2x2 = 1+(xy)2 ≡ 0 (mod p), which is impossible for p = 4m + 3 by Lemma 1. (5) If n is representable, and p = 4m + 3 divides n, then p2 divides n, and n/p2 is representable. This follows from (4), and completes the proof.
24 Representing numbers as sums of two squares Two remarks close our discussion: If a and b are two natural numbers that are relatively prime,then there are infinitely many primes of the form am+b(m E N)-this is a famous (and difficult)theorem of Dirichlet.More precisely,one can show that the number of primes p <x of the form p =am +b is described very accurately for large by the functionwherea)denotes the number of b with 1<b<a that are relatively prime to a.(This is a substantial refinement of the prime number theorem,which we had discussed on page 12.) This means that the primes for fixed a and varying b appear essentially at the same rate.Nevertheless,for example for a =4 one can observe a rather subtle,but still noticeable and persistent tendency towards"more" primes of the form 4m+3.The difference between the counts of primes of the form 4m+3 and those of the form 4m +1 changes sign infinitely often.Nevertheless,if you look for a large random z,then chances are that there are more primes p <x of the form p =4m+3 than of the form p 4m+1.This effect is known as "Chebyshev's bias";see Riesel [4]and Rubinstein and Sarnak [5]. References [1]F.W.CLARKE,W.N.EVERITT,L.L.LITTLEJOHN S.J.R.VORSTER: H.J.S.Smith and the Fermat Two Squares Theorem.Amer.Math.Monthly 106(1999),652-665. [2]D.R.HEATH-BROWN:Fermat's two squares theorem,Invariant(1984),2-5. [3]I.NIVEN H.S.ZUCKERMAN:An Introduction to the Theory of Numbers, Fifth edition,Wiley,New York 1972. [4]H.RIESEL:Prime Numbers and Computer Methods for Factorization,Second edition,Progress in Mathematics 126,Birkhauser,Boston MA 1994. [5]M.RUBINSTEIN P.SARNAK:Chebyshev's bias,Experimental Mathematics 3(1994).173-197 [6]A.THUE:Et par antydninger til en taltheoretisk metode,Kra.Vidensk.Selsk. Foh.7(1902),57-75. [7]S.WAGON:Editor's corner:The Euclidean algorithm strikes again,Amer. Math.Monthly97(1990),125-129. [8]D.ZAGIER:A one-sentence proof that every prime p =1(mod4)is a sum of two squares,Amer.Math.Monthly 97(1990),144
24 Representing numbers as sums of two squares Two remarks close our discussion: • If a and b are two natural numbers that are relatively prime, then there are infinitely many primes of the form am+b (m ∈ N) — this is a famous (and difficult) theorem of Dirichlet. More precisely, one can show that the number of primes p ≤ x of the form p = am + b is described very accurately for large x by the function 1 ϕ(a) x log x , where ϕ(a) denotes the number of b with 1 ≤ b<a that are relatively prime to a. (This is a substantial refinement of the prime number theorem, which we had discussed on page 12.) • This means that the primes for fixed a and varying b appear essentially at the same rate. Nevertheless, for example for a = 4 one can observe a rather subtle, but still noticeable and persistent tendency towards “more” primes of the form 4m + 3. The difference between the counts of primes of the form 4m + 3 and those of the form 4m + 1 changes sign infinitely often. Nevertheless, if you look for a large random x, then chances are that there are more primes p ≤ x of the form p = 4m + 3 than of the form p = 4m + 1. This effect is known as “Chebyshev’s bias”; see Riesel [4] and Rubinstein and Sarnak [5]. References [1] F. W. CLARKE, W. N. EVERITT, L. L. LITTLEJOHN & S. J. R. VORSTER: H. J. S. Smith and the Fermat Two Squares Theorem, Amer. Math. Monthly 106 (1999), 652-665. [2] D. R. HEATH-BROWN: Fermat’s two squares theorem, Invariant (1984), 2-5. [3] I. NIVEN & H. S. ZUCKERMAN: An Introduction to the Theory of Numbers, Fifth edition, Wiley, New York 1972. [4] H. RIESEL: Prime Numbers and Computer Methods for Factorization, Second edition, Progress in Mathematics 126, Birkhäuser, Boston MA 1994. [5] M. RUBINSTEIN & P. SARNAK: Chebyshev’s bias, Experimental Mathematics 3 (1994), 173-197. [6] A. THUE: Et par antydninger til en taltheoretisk metode, Kra. Vidensk. Selsk. Forh. 7 (1902), 57-75. [7] S. WAGON: Editor’s corner: The Euclidean algorithm strikes again, Amer. Math. Monthly 97 (1990), 125-129. [8] D. ZAGIER: A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares, Amer. Math. Monthly 97 (1990), 144
The law of quadratic reciprocity Chapter 5 Which famous mathematical theorem has been proved most often?Pythago- ras would certainly be a good candidate or the fundamental theorem of al- gebra,but the champion is without doubt the law of quadratic reciprocity in number theory.In an admirable monograph Franz Lemmermeyer lists as of the year 2000 no fewer than 196 proofs.Many of them are of course only slight variations of others,but the array of different ideas is still im- pressive,as is the list of contributors.Carl Friedrich Gauss gave the first complete proof in 1801 and followed up with seven more.A little later Ferdinand Gotthold Eisenstein added five more-and the ongoing list of provers reads like a Who is Who of mathematics. With so many proofs present the question which of them belongs in the Book can have no easy answer.Is it the shortest,the most unexpected,or should one look for the proof that had the greatest potential for general- izations to other and deeper reciprocity laws?We have chosen two proofs (based on Gauss'third and sixth proofs),of which the first may be the sim- plest and most pleasing,while the other is the starting point for fundamental Carl Friedrich Gauss results in more general structures. As in the previous chapter we work"modulo p",where p is an odd prime; Zp is the field of residues upon division by p,and we usually(but not al- ways)take these residues as 0,1,...,p-1.Consider some a0(mod p), that is,pfa.We call aa quadratic residue modulo p if a b2(mod p)for some b,and a quadratic nonresidue otherwise.The quadratic residues are therefore 12,22,....()2,and so there are quadratic residues and For p 13.the quadratic residues are quadratic nonresidues.Indeed,if=j(modp)with 1ij 12=1,22=4,32三9,42三3. then pli2-j2=(i-j)(i+j).As 2<i+j p-1 we have pli-j. 52≡12，and62≡10：the nonresidues that is,i≡j(modp). are2.5,6,7,8.11. At this point it is convenient to introduce the so-called Legendre symbol. Leta丰0(modp),then if a is a quadratic residue, if a is a quadratic nonresidue. The story begins with Fermat's"little theorem":For a0(modp), aP-1≡1(modp): (1) In fact,since Zp=p0}is a group with multiplication,the set [1a,2a,3a,...,(p-1)a}runs again through all nonzero residues, (1a(2a)…(p-1)a)≡1.2…(p-1)(modp), Alternatively,this is just alG =1 for the group G =Zp (see the box on and hence by dividing by (p-1)!,we get ap-1=1(modp). Lagrange's theorem,p.4). M.Aigner,G.M.Ziegler,Proofs from THE BOOK,DOI 10.1007/978-3-662-44205-0_5, @Springer-Verlag Berlin Heidelberg 2014
The law of quadratic reciprocity Chapter 5 Carl Friedrich Gauss Which famous mathematical theorem has been proved most often? Pythagoras would certainly be a good candidate or the fundamental theorem of algebra, but the champion is without doubt the law of quadratic reciprocity in number theory. In an admirable monograph Franz Lemmermeyer lists as of the year 2000 no fewer than 196 proofs. Many of them are of course only slight variations of others, but the array of different ideas is still impressive, as is the list of contributors. Carl Friedrich Gauss gave the first complete proof in 1801 and followed up with seven more. A little later Ferdinand Gotthold Eisenstein added five more — and the ongoing list of provers reads like a Who is Who of mathematics. With so many proofs present the question which of them belongs in the Book can have no easy answer. Is it the shortest, the most unexpected, or should one look for the proof that had the greatest potential for generalizations to other and deeper reciprocity laws? We have chosen two proofs (based on Gauss’ third and sixth proofs), of which the first may be the simplest and most pleasing, while the other is the starting point for fundamental results in more general structures. As in the previous chapter we work “modulo p”, where p is an odd prime; Zp is the field of residues upon division by p, and we usually (but not always) take these residues as 0, 1,...,p − 1. Consider some a ≡ 0 (mod p), that is, p a. We call a a quadratic residue modulo p if a ≡ b2 (mod p) for some b, and a quadratic nonresidue otherwise. The quadratic residues are therefore 12, 22,...,( p−1 2 )2, and so there are p−1 2 quadratic residues and p−1 2 quadratic nonresidues. Indeed, if i 2 ≡ j2(mod p) with 1 ≤ i, j ≤ p−1 2 , then p|i 2 − j2 = (i − j)(i + j). As 2 ≤ i + j ≤ p − 1 we have p|i − j, that is, i ≡ j (mod p). For p = 13, the quadratic residues are 12 ≡ 1, 22 ≡ 4, 32 ≡ 9, 42 ≡ 3, 52 ≡ 12, and 62 ≡ 10; the nonresidues are 2, 5, 6, 7, 8, 11. At this point it is convenient to introduce the so-called Legendre symbol. Let a ≡ 0 (mod p), then a p := 1 if a is a quadratic residue, −1 if a is a quadratic nonresidue. The story begins with Fermat’s “little theorem”: For a ≡ 0 (mod p), Alternatively, this is just a|G| = 1 for the group G = Z∗ p (see the box on Lagrange’s theorem, p. 4). ap−1 ≡ 1 (mod p). (1) In fact, since Z∗ p = Zp \ {0} is a group with multiplication, the set {1a, 2a, 3a, . . . ,(p − 1)a} runs again through all nonzero residues, (1a)(2a)···((p − 1)a) ≡ 1 · 2 ···(p − 1) (mod p), and hence by dividing by (p − 1)!, we get ap−1 ≡ 1 (mod p). M. Aigner, G.M. Ziegler, Proofs from THE BOOK, DOI 10.1007/978-3-662-44205-0_5, © Springer-Verlag Berlin Heidelberg 2014
26 The law of quadratic reciprocity In other words,the polynomial -1p has as roots all nonzero residues.Next we note that xP-1-1=(x学-1)（红学+1）. Suppose a =b2(modp)is a quadratic residue.Then by Fermat's little theorem a=1(modp).Hence the quadratic residues are precisely the roots of the first factor1 and thenonresidues must thus be the roots of the second factor+1.Comparing this to the definition of the Legendre symbol,we obtain the following important tool. For example,for p 17 and a 3 we have38=(34)2=812≡(-4)2≡ Euler's criterion.Fora0(modp). -1(mod 17),while for a 2 we get 28=(24)2≡(-1)2≡1(mod17). =a学(modp) Hence 2 is a quadratic residue,while 3 is a nonresidue. This gives us at once the important product rule 曾=99， (2) since this obviously holds for the right-hand side of Euler's criterion.The product rule is extremely helpful when one tries to compute Legendre sym- bols:Since any integer is a product of +1 and primes we only have to compute(帚)，(g),and(g)for odd primes, By Euler's criterion ()=1 if p=1(mod4).and ()=-1 if p= 3(mod 4),something we have already seen in the previous chapter.The case (will follow from the Lemma of Gauss below:()=1 if p ±1(mod8),while(层)=-1ifp三±3(mod8): Euler,Legendre,and Gauss did lots of calculations with quadratic residues and,in particular,studied the relations between g being a quadratic residue modulo p and p being a quadratic residue modulo g.when p and g are odd primes.Euler and Legendre thus discovered the following remarkable theorem,but they managed to prove it only in special cases.However, Gauss was successful:On April 8,1796 he was proud to record in his diary the first full proof. Law of quadratic reciprocity.Let p and q be different odd primes. Then ()=(-1)学学 If p 1(mod4)or =1(mod4),then (resp.)is even,and therefore(-1)学号=1；thus(g)=().When p三g三3(mod4,we Example:()=()=()=-1.have (2)=-(2).Thus for odd primes we get (2)=()unless both p so 3 is a nonresidue mod 17. and g are congruent to 3(mod 4)
26 The law of quadratic reciprocity In other words, the polynomial xp−1 − 1 ∈ Zp[x] has as roots all nonzero residues. Next we note that xp−1 − 1=(x p−1 2 − 1)(x p−1 2 + 1). Suppose a ≡ b2 (mod p) is a quadratic residue. Then by Fermat’s little theorem a p−1 2 ≡ bp−1 ≡ 1 (mod p). Hence the quadratic residues are precisely the roots of the first factor x p−1 2 − 1, and the p−1 2 nonresidues must thus be the roots of the second factor x p−1 2 + 1. Comparing this to the definition of the Legendre symbol, we obtain the following important tool. Euler’s criterion. For a ≡ 0 (mod p), a p ≡ a p−1 2 (mod p). For example, for p = 17 and a = 3 we have 38 = (34) 2 = 812 ≡ (−4)2 ≡ −1 (mod 17), while for a = 2 we get 28 = (24) 2 ≡ (−1)2 ≡ 1 (mod 17). Hence 2 is a quadratic residue, while 3 is a nonresidue. This gives us at once the important product rule ab p = a p b p , (2) since this obviously holds for the right-hand side of Euler’s criterion. The product rule is extremely helpful when one tries to compute Legendre symbols: Since any integer is a product of ±1 and primes we only have to compute ( −1 p ), ( 2 p ), and ( q p ) for odd primes q. By Euler’s criterion ( −1 p )=1 if p ≡ 1 (mod 4), and ( −1 p ) = −1 if p ≡ 3 (mod 4), something we have already seen in the previous chapter. The case ( 2 p ) will follow from the Lemma of Gauss below: ( 2 p )=1 if p ≡ ±1 (mod 8), while ( 2 p ) = −1 if p ≡ ±3 (mod 8). Euler, Legendre, and Gauss did lots of calculations with quadratic residues and, in particular, studied the relations between q being a quadratic residue modulo p and p being a quadratic residue modulo q, when p and q are odd primes. Euler and Legendre thus discovered the following remarkable theorem, but they managed to prove it only in special cases. However, Gauss was successful: On April 8, 1796 he was proud to record in his diary the first full proof. Law of quadratic reciprocity. Let p and q be different odd primes. Then ( q p )(p q )=(−1) p−1 2 q−1 2 . If p ≡ 1 (mod 4) or q ≡ 1 (mod 4), then p−1 2 (resp. q−1 2 ) is even, and therefore (−1) p−1 2 q−1 2 = 1; thus ( q p )=( p q ). When p ≡ q ≡ 3 (mod 4), we have ( p q ) = −( q p ). Thus for odd primes we get ( p q )=( q p ) unless both p and q are congruent to 3 (mod 4). Example: ( 3 17 )=( 17 3 )=( 2 3 ) = −1, so 3 is a nonresidue mod 17