Representing numbers Chapter 4 as sums of two squares 1=12+02 Which numbers can be written as sums of two squares? 2=12+12 3= 4=22+02 This question is as old as number theory,and its solution is a classic in the 5=22+12 field.The "hard"part of the solution is to see that every prime number of 6= the form 4m +1 is a sum of two squares.G.H.Hardy writes that this 7= two square theorem of Fermat"is ranked,very justly,as one of the finest in 8=22+22 arithmetic."Nevertheless,one of our Book Proofs below is quite recent. 9=32+ Let's start with some"warm-ups."First,we need to distinguish between 10=321 the prime p =2,the primes of the form p =4m+1,and the primes of 11= the form p=4m +3.Every prime number belongs to exactly one of these three classes.At this point we may note (using a method"a la Euclid")that there are infinitely many primes of the form 4m+3.In fact,if there were only finitely many,then we could take p&to be the largest prime of this form.Setting Nk=22.3.5…pk-1 (where pi =2,p2 =3,p3 =5,...denotes the sequence of all primes),we find that Nk is congruent to 3(mod 4),so it must have a prime factor of the form 4m +3,and this prime factor is larger than pk-contradiction. Our first lemma characterizes the primes for which-1 is a square in the Pierre de Fermat field Zp(which is reviewed in the box on the next page).It will also give us a quick way to derive that there are infinitely many primes of the form 4m+1. Lemma 1.For primes p=4m+1 the equation s2=-1(modp)has two solutions s∈{1,2，.，p-l},forp=2 there is one such solution,while for primes of the form p=4m +3 there is no solution. Proof.For p 2 take s 1.For odd p,we construct the equivalence relation on {1,2,...,p-1}that is generated by identifying every element with its additive inverse and with its multiplicative inverse in Zp.Thus the "general"equivalence classes will contain four elements {x,-x,工，- since such a 4-element set contains both inverses for all its elements.How- ever,there are smaller equivalence classes if some of the four numbers are not distinct: M.Aigner,G.M.Ziegler,Proofs from THE BOOK,DOI 10.1007/978-3-662-44205-0_4, @Springer-Verlag Berlin Heidelberg 2014Representing numbers as sums of two squares Chapter 4 Pierre de Fermat 1=12 + 02 2=12 + 12 3 = 4=22 + 02 5=22 + 12 6 = 7 = 8=22 + 22 9=32 + 10 = 32 + 11 =. . . Which numbers can be written as sums of two squares? This question is as old as number theory, and its solution is a classic in the field. The “hard” part of the solution is to see that every prime number of the form 4m + 1 is a sum of two squares. G. H. Hardy writes that this two square theorem of Fermat “is ranked, very justly, as one of the finest in arithmetic.” Nevertheless, one of our Book Proofs below is quite recent. Let’s start with some “warm-ups.” First, we need to distinguish between the prime p = 2, the primes of the form p = 4m + 1, and the primes of the form p = 4m + 3. Every prime number belongs to exactly one of these three classes. At this point we may note (using a method “à la Euclid”) that there are infinitely many primes of the form 4m + 3. In fact, if there were only finitely many, then we could take pk to be the largest prime of this form. Setting Nk := 22 · 3 · 5 ··· pk − 1 (where p1 = 2, p2 = 3, p3 = 5, . . . denotes the sequence of all primes), we find that Nk is congruent to 3 (mod 4), so it must have a prime factor of the form 4m + 3, and this prime factor is larger than pk — contradiction. Our first lemma characterizes the primes for which −1 is a square in the field Zp (which is reviewed in the box on the next page). It will also give us a quick way to derive that there are infinitely many primes of the form 4m + 1. Lemma 1. For primes p = 4m + 1 the equation s2 ≡ −1 (mod p) has two solutions s ∈ {1, 2, . . ., p−1}, for p = 2 there is one such solution, while for primes of the form p = 4m + 3 there is no solution. Proof. For p = 2 take s = 1. For odd p, we construct the equivalence relation on {1, 2,...,p − 1} that is generated by identifying every element with its additive inverse and with its multiplicative inverse in Zp. Thus the “general” equivalence classes will contain four elements {x, −x, x, −x} since such a 4-element set contains both inverses for all its elements. How￾ever, there are smaller equivalence classes if some of the four numbers are not distinct: M. Aigner, G.M. Ziegler, Proofs from THE BOOK, DOI 10.1007/978-3-662-44205-0_4, © Springer-Verlag Berlin Heidelberg 2014