Binomial coefficients are (almost)never powers 17 So for each i the number of multiples of p'among n,...,n-k+1,and hence among the a,'s,is bounded by+1.This implies that the expo- nent of p in aoa1...ak-1 is at most + with the reasoning that we used for Legendre's theorem in Chapter 2.The only difference is that this time the sum stops at i =-1,since the aj's contain no e-th powers. Taking both counts together,we find that the exponent of p in v is at most (制+)-制 ≤-1， i1 i1 and we have our desired contradiction,since vt is an e-th power. This suffices already to settle the case e=2.Indeed,since k>4 one of We see that our analysis so far agrees the a's must be equal to 4.but the a's contain no squares.So let us now with ()=1402.as assume that e≥3. 50=2.52 (4)Sincek 4,we must have ai 1,aiz=2,aia =4 for some i1,i2,i3. 49=1.72 that is, 48=3.42 and5.7.4=140. n-i1 mi:n-i2 2m2,n-i3 4mg. We claim that (n-i2)2 (n-i1)(n -i3).If not,put b n i2 and n-i1=b-t,n-i3=b+y,where 0<,ly<k.Hence 62=(b-z)(b+y)or (y-x)b=IV, where z=y is plainly impossible.Now we have by part(1) lz=ly-x≥b>n-k>(k-1)2≥x, which is absurd. So we have mz mim3,where we assume m>mim3(the other case being analogous),and proceed to our last chains of inequalities.We obtain 2(k-1)n>n2-(n-k+1)2>(n-i2)2-(m-i1)(n-ig) =4[m-(m1m3)≥4(m1m3+1)-(m1m3)1 ≥4lmf-lm5-1. Since≥3andn>kt≥k3>6k,this yields 2(k-1)nmim3 4emims e(n-i1)(n-i3) >4n-k+12>3n-62>2m2
Binomial coefficients are (almost) never powers 17 So for each i the number of multiples of pi among n, . . . , n−k+1, and hence among the aj ’s, is bounded by k pi + 1. This implies that the exponent of p in a0a1 ··· ak−1 is at most −1 i=1 k pi + 1 with the reasoning that we used for Legendre’s theorem in Chapter 2. The only difference is that this time the sum stops at i = − 1, since the aj ’s contain no -th powers. Taking both counts together, we find that the exponent of p in v is at most −1 i=1 k pi + 1 − i≥1 k pi ≤ − 1, and we have our desired contradiction, since v is an -th power. We see that our analysis so far agrees with 50 3 = 1402, as 50 = 2 · 52 49 = 1 · 72 48 = 3 · 42 and 5 · 7 · 4 = 140. This suffices already to settle the case = 2. Indeed, since k ≥ 4 one of the ai’s must be equal to 4, but the ai’s contain no squares. So let us now assume that ≥ 3. (4) Since k ≥ 4, we must have ai1 = 1, ai2 = 2, ai3 = 4 for some i1, i2, i3, that is, n − i1 = m 1, n − i2 = 2m 2, n − i3 = 4m 3. We claim that (n − i2)2 = (n − i1)(n − i3). If not, put b = n − i2 and n − i1 = b − x, n − i3 = b + y, where 0 < |x|, |y| < k. Hence b2 = (b − x)(b + y) or (y − x)b = xy, where x = y is plainly impossible. Now we have by part (1) |xy| = b|y − x| ≥ b>n − k > (k − 1)2 ≥ |xy|, which is absurd. So we have m2 2 = m1m3, where we assume m2 2 > m1m3 (the other case being analogous), and proceed to our last chains of inequalities. We obtain 2(k − 1)n>n2 − (n − k + 1)2 > (n − i2) 2 − (n − i1)(n − i3) = 4[m2 2 − (m1m3) ] ≥ 4[(m1m3 + 1) − (m1m3) ] ≥ 4m−1 1 m−1 3 . Since ≥ 3 and n>k ≥ k3 > 6k, this yields 2(k − 1)nm1m3 > 4m 1m 3 = (n − i1)(n − i3) > (n − k + 1)2 > 3(n − n 6 ) 2 > 2n2.
18 Binomial coefficients are (almost)never powers Now since mi≤n/e≤n/3 we finally obtain kn2/3 kmim3 (k-1)mim3 n, or k3>n.With this contradiction,the proof is complete. 口 References [1]P.ERDOS:A theorem of Sylvester and Schur.J.London Math.Soc.9 (1934). 282-288. [2]P.ERDOS:On a diophantine equation,J.London Math.Soc.26 (1951). 176-178. [3]J.J.SYLVESTER:On arithmetical series,Messenger of Math.21(1892),1-19, 87-120:Collected Mathematical Papers Vol.4,1912,687-731
18 Binomial coefficients are (almost) never powers Now since mi ≤ n1/ ≤ n1/3 we finally obtain kn2/3 ≥ km1m3 > (k − 1)m1m3 > n, or k3 > n. With this contradiction, the proof is complete. References [1] P. ERDOS˝ : A theorem of Sylvester and Schur, J. London Math. Soc. 9 (1934), 282-288. [2] P. ERDOS˝ : On a diophantine equation, J. London Math. Soc. 26 (1951), 176-178. [3] J. J. SYLVESTER: On arithmetical series, Messenger of Math. 21 (1892), 1-19, 87-120; Collected Mathematical Papers Vol. 4, 1912, 687-731.
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 2014
Representing 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. However, 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
20 Representing numbers as sums of two squares ●x≡-x is impossible for odd p. ·x≡is equivalent to2≡l.This has two solutions,namely x=1 and =p-1,leading to the equivalence class {1,p-1}of size 2. .=-is equivalent to r2=-1.This equation may have no solution or two distinct solutions zo,p-xo:in this case the equivalence class is {xo,p-xof. For p =11 the partition is The set {1,2,...,p-1}has p-1 elements,and we have partitioned it into {1,10},{2,9,6,5},{3,8,4,7}: quadruples (equivalence classes of size 4),plus one or two pairs(equiva- for p=13 it is lence classes of size 2).For p-1=4m+2 we find that there is only the {1,12},{2,11,7,6},{3,10,9,4}, one pair {1,p-1,the rest is quadruples,and thus s2=-1(mod p)has no 15,8):the pair (5,8}yields the two solution.For p-1 4m there has to be the second pair,and this contains solutions of s2=-1 mod 13. the two solutions of s2=-1 that we were looking for. ▣ Lemma 1 says that every odd prime dividing a number M2+1 must be of the form 4m+1.This implies that there are infinitely many primes of this form:Otherwise,look at(2.3.5...)2+1,where a is the largest such prime.The same reasoning as above yields a contradiction. Prime fields If p is a prime,then the set p =(0,1,...,p-1)with addition and multiplication defined"modulo p"forms a finite field.We will need the following simple properties: ·Forx∈Zp,x≠O,the additive inverse(for which we usually +|01234 write-x)is given by p-x∈{1,2，..，p-l}.fp>2,thenx 001234 and -x are different elements of Zp. 112340 2 23401 ·Eachx∈Zp\{O}has a unique multiplicative inverse∈Zp\{O}, 3 34012 with r元≡1(modp) 440123 The definition of primes implies that the mapppxz is injective for0.Thus on the finite set Zp\o}it must be .01234 surjective as well,and hence for each x there is a unique 0 000000 with z元≡1(modp): 101234 2 02413 The squares 02,12,22,...,h2 define different elements of Zp.for 3 03142 h=l」 404321 This is since2=y2,or(x+y)(r-gy)≡0，implies that三y Addition and multiplication in Zs or that x =-y.The 1+elements 02,12,...,h2 are called the squares in Zp. At this point,let us note "on the fly"that for all primes there are solutions for 2+y2=-1(modp).In fact,there are 1 distinct squares z2 in Zp,and there are+1 distinct numbers of the form -(1+y). These two sets of numbers are too large to be disjoint,since Zp has only p elements,and thus there must exist z and y with 2=-(1+y2)(modp)
20 Representing numbers as sums of two squares • x ≡ −x is impossible for odd p. • x ≡ x is equivalent to x2 ≡ 1. This has two solutions, namely x = 1 and x = p − 1, leading to the equivalence class {1, p − 1} of size 2. • x ≡ −x is equivalent to x2 ≡ −1. This equation may have no solution or two distinct solutions x0, p − x0: in this case the equivalence class is {x0, p − x0}. For p = 11 the partition is {1, 10}, {2, 9, 6, 5}, {3, 8, 4, 7}; for p = 13 it is {1, 12}, {2, 11, 7, 6}, {3, 10, 9, 4}, {5, 8}: the pair {5, 8} yields the two solutions of s2 ≡ −1 mod 13. The set {1, 2,...,p−1} has p−1 elements, and we have partitioned it into quadruples (equivalence classes of size 4), plus one or two pairs (equivalence classes of size 2). For p − 1=4m + 2 we find that there is only the one pair {1, p−1}, the rest is quadruples, and thus s2 ≡ −1 (mod p) has no solution. For p − 1=4m there has to be the second pair, and this contains the two solutions of s2 ≡ −1 that we were looking for. Lemma 1 says that every odd prime dividing a number M2 + 1 must be of the form 4m + 1. This implies that there are infinitely many primes of this form: Otherwise, look at (2 · 3 · 5 ··· qk)2 + 1, where qk is the largest such prime. The same reasoning as above yields a contradiction. + 01234 0 01234 1 12340 2 23401 3 34012 4 40123 · 01234 0 00000 1 01234 2 02413 3 03142 4 04321 Addition and multiplication in Z5 Prime fields If p is a prime, then the set Zp = {0, 1,...,p − 1} with addition and multiplication defined “modulo p” forms a finite field. We will need the following simple properties: • For x ∈ Zp, x = 0, the additive inverse (for which we usually write −x) is given by p − x ∈ {1, 2,...,p − 1}. If p > 2, then x and −x are different elements of Zp. • Each x ∈ Zp\{0} has a unique multiplicative inverse x ∈ Zp\{0}, with xx ≡ 1 (mod p). The definition of primes implies that the map Zp → Zp, z → xz is injective for x = 0. Thus on the finite set Zp\{0} it must be surjective as well, and hence for each x there is a unique x = 0 with xx ≡ 1 (mod p). • The squares 02, 12, 22,...,h2 define different elements of Zp, for h = p 2 . This is since x2 ≡ y2, or (x + y)(x − y) ≡ 0, implies that x ≡ y or that x ≡ −y. The 1 + p 2 elements 02, 12,...,h2 are called the squares in Zp. At this point, let us note “on the fly” that for all primes there are solutions for x2 + y2 ≡ −1 (mod p). In fact, there are p 2 + 1 distinct squares x2 in Zp, and there are p 2 + 1 distinct numbers of the form −(1 + y2). These two sets of numbers are too large to be disjoint, since Zp has only p elements, and thus there must exist x and y with x2 ≡ −(1 + y2) (mod p).
Representing numbers as sums of two squares 21 Lemma 2.No number n =4m +3 is a sum of two squares. Proof.The square of any even number is(2k)2=4k2=0(mod 4), while squares of odd numbers yield (2+1)2=4()+1=1(mod 4). Thus any sum of two squares is congruent to 0,1 or 2(mod 4). 口 This is enough evidence for us that the primes p =4m+3 are "bad."Thus, we proceed with"good"properties for primes of the form p =4m+1.On the way to the main theorem,the following is the key step. Proposition.Every prime of the form p 4m+1 is a sum of two squares, that is,it can be written as p=x2+y2 for some natural numbers r,y E N. We shall present here two proofs of this result-both of them elegant and surprising.The first proof features a striking application of the "pigeon- hole principle"(which we have already used"on the fly"before Lemma 2; see Chapter 27 for more),as well as a clever move to arguments"modulo p" and back.The idea is due to the Norwegian number theorist Axel Thue. ■Proof..Consider the pairs(x',y)of integers with0≤x',y≤√p,that is,x,y∈{0,1，，L}.There are(LV+l)2 such pairs.Using the estimate x+1>x for x=vp,we see that we have more than p such pairs of integers.Thus for any s EZ,it is impossible that all the values For p 13,[vp]3 we consider x'-sy'produced by the pairs ('y)are distinct modulo p.That is,for ',y'(0,1,2,3).For s =5,the sum every s there are two distinct pairs r'-sy'(mod 13)assumes the following values: (x,),(z”,"∈{0,1，LV}2 01 23 with '-sy'="-sy"(modp).Now we take differences:We have 008311 '-x"=s(y-y")(modp).Thus if we define '".y= 1 19412 ly'-y"I,then we get 2 2105 0 (z,)∈{0,1，.，Lv}2 with z=±sy(modp). 3 3116 1 Also we know that not both x and y can be zero,because the pairs(',y) and (",y")are distinct. Now let s be a solution of s2 =-1(modp),which exists by Lemma 1. Then x2=s2y2=-y2(modp),and so we have produced (,y)Z2 with 0<2+y2<2p and2+y2=0(modp). But p is the only number between 0 and 2p that is divisible by p.Thus x2+y2=p:done! ▣ Our second proof for the proposition-also clearly a Book Proof- was discovered by Roger Heath-Brown in 1971 and appeared in 1984. (A condensed"one-sentence version"was given by Don Zagier.)It is so elementary that we don't even need to use Lemma 1. Heath-Brown's argument features three linear involutions:a quite obvious one,a hidden one,and a trivial one that gives"the final blow.The second, unexpected,involution corresponds to some hidden structure on the set of integral solutions of the equation 4xy+22=p
Representing numbers as sums of two squares 21 Lemma 2. No number n = 4m + 3 is a sum of two squares. Proof. The square of any even number is (2k)2 = 4k2 ≡ 0 (mod 4), while squares of odd numbers yield (2k+1)2 = 4(k2+k)+1 ≡ 1 (mod 4). Thus any sum of two squares is congruent to 0, 1 or 2 (mod 4). This is enough evidence for us that the primes p = 4m+ 3 are “bad.” Thus, we proceed with “good” properties for primes of the form p = 4m + 1. On the way to the main theorem, the following is the key step. Proposition. Every prime of the form p = 4m+ 1 is a sum of two squares, that is, it can be written as p = x2 +y2 for some natural numbers x, y ∈ N. We shall present here two proofs of this result — both of them elegant and surprising. The first proof features a striking application of the “pigeonhole principle” (which we have already used “on the fly” before Lemma 2; see Chapter 27 for more), as well as a clever move to arguments “modulo p” and back. The idea is due to the Norwegian number theorist Axel Thue. Proof. Consider the pairs (x , y ) of integers with 0 ≤ x , y ≤ √p, that is, x , y ∈ {0, 1,..., √p }. There are ( √p + 1)2 such pairs. Using the estimate x + 1 > x for x = √p, we see that we have more than p such pairs of integers. Thus for any s ∈ Z, it is impossible that all the values x − sy produced by the pairs (x , y ) are distinct modulo p. That is, for every s there are two distinct pairs (x , y ), (x, y) ∈ {0, 1,..., √p }2 with x − sy ≡ x − sy (mod p). Now we take differences: We have For p = 13, √p = 3 we consider x , y ∈ {0, 1, 2, 3}. For s = 5, the sum x −sy (mod 13) assumes the following values: x ◗◗ y 0123 0 0 8 3 11 1 1 9 4 12 2 2 10 5 0 3 3 11 6 1 x − x ≡ s(y − y) (mod p). Thus if we define x := |x − x|, y := |y − y|, then we get (x, y) ∈ {0, 1,..., √p }2 with x ≡ ±sy (mod p). Also we know that not both x and y can be zero, because the pairs (x , y ) and (x, y) are distinct. Now let s be a solution of s2 ≡ −1 (mod p), which exists by Lemma 1. Then x2 ≡ s2y2 ≡ −y2 (mod p), and so we have produced (x, y) ∈ Z2 with 0 < x2 + y2 < 2p and x2 + y2 ≡ 0 (mod p). But p is the only number between 0 and 2p that is divisible by p. Thus x2 + y2 = p: done! Our second proof for the proposition — also clearly a Book Proof — was discovered by Roger Heath-Brown in 1971 and appeared in 1984. (A condensed “one-sentence version” was given by Don Zagier.) It is so elementary that we don’t even need to use Lemma 1. Heath-Brown’s argument features three linear involutions: a quite obvious one, a hidden one, and a trivial one that gives “the final blow.” The second, unexpected, involution corresponds to some hidden structure on the set of integral solutions of the equation 4xy + z2 = p.