Number Theory 1 Six proofs of the infinity of primes 3 2 Bertrand's postulate 9 3 Binomial coefficients are(almost)never powers 15 4 Representing numbers as sums of two squares 19 5 The law of quadratic reciprocity 25 6 Every finite division ring is a field 33 7 The spectral theorem and Hadamard's determinant problem 37 8 Some irrational numbers 45 9 Three timesπ2/653 “Irrationality and
Number Theory 1 Six proofs of the infinity of primes 3 2 Bertrand’s postulate 9 3 Binomial coefficients are (almost) never powers 15 4 Representing numbers as sums of two squares 19 5 The law of quadratic reciprocity 25 6 Every finite division ring is a field 33 7 The spectral theorem and Hadamard’s determinant problem 37 8 Some irrational numbers 45 9 Three times π2/6 53 “Irrationality and π
Six proofs Chapter 1 of the infinity of primes It is only natural that we start these notes with probably the oldest Book Proof,usually attributed to Euclid (Elements IX,20).It shows that the sequence of primes does not end. Euclid's Proof.For any finite set {pi,...,pr}of primes,consider the number n pip2...pr+1.This n has a prime divisor p.But p is not one of the pi:otherwise p would be a divisor of n and of the product pip2...pr,and thus also of the difference n-pip2...p =1,which is impossible.So a finite set [p1,...,pr}cannot be the collection of all prime numbers. ▣ Before we continue let us fix some notation.N={1,2,3,...}is the set of natural numbers,=f...,-2,-1,0,1,2,...!the set of integers,and P=12,3,5,7,...}the set of primes. In the following,we will exhibit various other proofs (out of a much longer list)which we hope the reader will like as much as we do.Although they use different view-points,the following basic idea is common to all of them: The natural numbers grow beyond all bounds,and every natural number n 2 has a prime divisor.These two facts taken together force P to be infinite.The next proof is due to Christian Goldbach(from a letter to Leon- hard Euler 1730),the third proof is apparently folklore,the fourth one is by Euler himself,the fifth proof was proposed by Harry Furstenberg,while the last proof is due to Paul Erdos. Second Proof.Let us first look at the Fermat numbers Fn=22"+1for Fo =3 F =5 n =0,1,2,....We will show that any two Fermat numbers are relatively F2 =17 prime;hence there must be infinitely many primes.To this end,we verify F =257 the recursion n-1 F4= 65537 R=-2(m≥1)， Fs =641.6700417 k=0 The first few Fermat numbers from which our assertion follows immediately.Indeed,if m is a divisor of, say,Fk and Fn (k<n),then m divides 2,and hence m 1 or 2.But m=2 is impossible since all Fermat numbers are odd. To prove the recursion we use induction on n.For n =1 we have Fo =3 and F1-2 =3.With induction we now conclude ⅡA=()=G-, n-l =(22"-1)(22"+1)=22m+-1=F+1-2. ▣ M.Aigner,G.M.Ziegler,Proofs from THE BOOK,DOI 10.1007/978-3-662-44205-0_1, @Springer-Verlag Berlin Heidelberg 2014
Six proofs of the infinity of primes Chapter 1 It is only natural that we start these notes with probably the oldest Book Proof, usually attributed to Euclid (Elements IX, 20). It shows that the sequence of primes does not end. Euclid’s Proof. For any finite set {p1,...,pr} of primes, consider the number n = p1p2 ··· pr + 1. This n has a prime divisor p. But p is not one of the pi: otherwise p would be a divisor of n and of the product p1p2 ··· pr, and thus also of the difference n − p1p2 ··· pr = 1, which is impossible. So a finite set {p1,...,pr} cannot be the collection of all prime numbers. Before we continue let us fix some notation. N = {1, 2, 3,...} is the set of natural numbers, Z = {..., −2, −1, 0, 1, 2,...} the set of integers, and P = {2, 3, 5, 7,...} the set of primes. In the following, we will exhibit various other proofs (out of a much longer list) which we hope the reader will like as much as we do. Although they use different view-points, the following basic idea is common to all of them: The natural numbers grow beyond all bounds, and every natural number n ≥ 2 has a prime divisor. These two facts taken together force P to be infinite. The next proof is due to Christian Goldbach (from a letter to Leonhard Euler 1730), the third proof is apparently folklore, the fourth one is by Euler himself, the fifth proof was proposed by Harry Fürstenberg, while the last proof is due to Paul Erdos. ˝ Second Proof. Let us first look at the Fermat numbers Fn = 22n +1 for n = 0, 1, 2,.... We will show that any two Fermat numbers are relatively prime; hence there must be infinitely many primes. To this end, we verify the recursion n −1 k=0 Fk = Fn − 2 (n ≥ 1), from which our assertion follows immediately. Indeed, if m is a divisor of, F0 = 3 F1 = 5 F2 = 17 F3 = 257 F4 = 65537 F5 = 641 · 6700417 The first few Fermat numbers say, Fk and Fn (k<n), then m divides 2, and hence m = 1 or 2. But m = 2 is impossible since all Fermat numbers are odd. To prove the recursion we use induction on n. For n = 1 we have F0 = 3 and F1 − 2=3. With induction we now conclude n k=0 Fk = n −1 k=0 Fk Fn = (Fn − 2)Fn = = (22n − 1)(22n + 1) = 22n+1 − 1 = Fn+1 − 2. M. Aigner, G.M. Ziegler, Proofs from THE BOOK, DOI 10.1007/978-3-662-44205-0_1, © Springer-Verlag Berlin Heidelberg 2014
Six proofs of the infinity of primes Third Proof.Suppose P is finite and pis the largest prime.We consider Lagrange's theorem the so-called Mersenne number 2P-1 and show that any prime factor q If G is a finite(multiplicative)group of 2P-1 is bigger than p,which will yield the desired conclusion.Let g be and U is a subgroup.then U a prime dividing 2P-1,so we have 2P=1(mod g).Since p is prime,this divides G. means that the element 2 has order p in the multiplicative group Zo}of Proof.Consider the binary rela- the field Za.This group has q-1 elements.By Lagrange's theorem (see tion the box)we know that the order of every element divides the size of the a~b:←→ba-1∈U. group,that is,we have pq-1,and hence p<q. 0 It follows from the group axioms Now let us look at a proof that uses elementary calculus. that is an equivalence relation. ■Fourth Proof.Letπ(x=#{p≤x:p∈P}be the number of primes The equivalence class containing an that are less than or equal to the real number x.We number the primes element a is precisely the coset P [pi,p2,p3,...}in increasing order.Consider the natural logarithm Ua={xa:x∈U} logz,defined as log x=dt. Since clearly Ual U.we find Now we compare the area below the graph of f(t)=with an upper step function.(See also the appendix on page 12 for this method.)Thus for that G decomposes into equivalence n≤x<n+1 we have classes,all of size U,and hence that U divides G. 口 11 logx ≤1++号+…+n+分 In the special case when U is a cyclic subgroup fa,a2,...,am}we find ≤ -where the sum extends over all m EN which have that m (the smallest positive inte- only prime divisors p <x. ger such that a"=1,called the order of a)divides the size G of Since every such m can be written in a unique way as a product of the form the group.In particular,we have II pr,we see that the last sum is equal to alGl 1. P<I pEP p<I The inner sum is a geometric series with ratiohence π(x) logx≤ 0 PEP P<I p<x 1 2 nn+l Now clearly pk>k+1,and thus Steps above the functionf(t)= Pk ≤1+= 1 Pk-1 =1+ and therefore x( logx≤ k+1 =T(x)+1. k=1 Everybody knows that logz is not bounded,so we conclude that m()is unbounded as well,and so there are infinitely many primes
4 Six proofs of the infinity of primes Third Proof. Suppose P is finite and p is the largest prime. We consider the so-called Mersenne number 2p − 1 and show that any prime factor q of 2p − 1 is bigger than p, which will yield the desired conclusion. Let q be a prime dividing 2p − 1, so we have 2p ≡ 1 (mod q). Since p is prime, this Lagrange’s theorem If G is a finite (multiplicative) group and U is a subgroup, then |U| divides |G|. Proof. Consider the binary relation a ∼ b : ⇐⇒ ba−1 ∈ U. It follows from the group axioms that ∼ is an equivalence relation. The equivalence class containing an element a is precisely the coset Ua = {xa : x ∈ U}. Since clearly |Ua| = |U|, we find that G decomposes into equivalence classes, all of size |U|, and hence that |U| divides |G|. In the special case when U is a cyclic subgroup {a, a2,...,am} we find that m (the smallest positive integer such that am = 1, called the order of a) divides the size |G| of the group. In particular, we have a|G| = 1. means that the element 2 has order p in the multiplicative group Zq\{0} of the field Zq. This group has q − 1 elements. By Lagrange’s theorem (see the box) we know that the order of every element divides the size of the group, that is, we have p | q − 1, and hence p<q. Now let us look at a proof that uses elementary calculus. Fourth Proof. Let π(x) := #{p ≤ x : p ∈ P} be the number of primes that are less than or equal to the real number x. We number the primes P = {p1, p2, p3,...} in increasing order. Consider the natural logarithm log x, defined as log x = x 1 1 t dt. 21 1 n n+1 Steps above the function f(t) = 1 t Now we compare the area below the graph of f(t) = 1 t with an upper step function. (See also the appendix on page 12 for this method.) Thus for n ≤ x<n + 1 we have log x ≤ 1 + 1 2 + 1 3 + ··· + 1 n − 1 + 1 n ≤ 1 m, where the sum extends over all m ∈ N which have only prime divisors p ≤ x. Since every such m can be written in a unique way as a product of the form p≤x pkp , we see that the last sum is equal to p∈P p≤x k≥0 1 pk . The inner sum is a geometric series with ratio 1 p , hence log x ≤ p∈P p≤x 1 1 − 1 p = p∈P p≤x p p − 1 = π (x) k=1 pk pk − 1 . Now clearly pk ≥ k + 1, and thus pk pk − 1 = 1+ 1 pk − 1 ≤ 1 + 1 k = k + 1 k , and therefore log x ≤ π (x) k=1 k + 1 k = π(x)+1. Everybody knows that log x is not bounded, so we conclude that π(x) is unbounded as well, and so there are infinitely many primes.
Six proofs of the infinity of primes J Fifth Proof.After analysis it's topology now!Consider the following curious topology on the set Z of integers.For a,bZ,b>0,we set Na.b={a+nb:n∈Z. Each set N is a two-way infinite arithmetic progression.Now call a set O CZ open if either O is empty,or if to every a E O there exists some b>0 with Na.b O.Clearly,the union of open sets is open again.If 01,02 are open,and a nO2 with Na.b O1 and Na.baO2. then a E Na.bbO1nO2.So we conclude that any finite intersection of open sets is again open.So,this family of open sets induces a bona fide topology on Z. Let us note two facts: (A)Any nonempty open set is infinite. (B)Any set Na.b is closed as well. Indeed,the first fact follows from the definition.For the second we observe b-1 Na.b =Z Nati.b; i=1 which proves that Na.b is the complement of an open set and hence closed. So far the primes have not yet entered the picture-but here they come. Since any number n1,-1 has a prime divisor p,and hence is contained in No.p,we conclude Z\{1,-1}No.p. "Pitching flat rocks,infinitely" pEp Now if P were finite,then No.p would be a finite union of closed sets (by (B)),and hence closed.Consequently,{1,-1 would be an open set, in violation of (A). ▣ Sixth Proof.Our final proof goes a considerable step further and demonstrates not only that there are infinitely many primes,but also that the seriesdiverges.The first proof of this important result was given by Euler(and is interesting in its own right),but our proof,devised by Erdos,is of compelling beauty. Let pi,p2,p3,...be the sequence of primes in increasing order,and assume that∑pee。 converges.Then there must be a natural numberk such that∑≥kt<子.Let us call p,,p the small primes,and Pk+1,Pk+2,...the big primes.For an arbitrary natural number N we there- fore find (1)
Six proofs of the infinity of primes 5 Fifth Proof. After analysis it’s topology now! Consider the following curious topology on the set Z of integers. For a, b ∈ Z, b > 0, we set Na,b = {a + nb : n ∈ Z}. Each set Na,b is a two-way infinite arithmetic progression. Now call a set O ⊆ Z open if either O is empty, or if to every a ∈ O there exists some b > 0 with Na,b ⊆ O. Clearly, the union of open sets is open again. If O1, O2 are open, and a ∈ O1 ∩ O2 with Na,b1 ⊆ O1 and Na,b2 ⊆ O2, then a ∈ Na,b1b2 ⊆ O1 ∩ O2. So we conclude that any finite intersection of open sets is again open. So, this family of open sets induces a bona fide topology on Z. Let us note two facts: (A) Any nonempty open set is infinite. (B) Any set Na,b is closed as well. Indeed, the first fact follows from the definition. For the second we observe Na,b = Z \ b −1 i=1 Na+i,b, which proves that Na,b is the complement of an open set and hence closed. “Pitching flat rocks, infinitely” So far the primes have not yet entered the picture — but here they come. Since any number n = 1, −1 has a prime divisor p, and hence is contained in N0,p, we conclude Z \ {1, −1} = p∈P N0,p. Now if P were finite, then p∈P N0,p would be a finite union of closed sets (by (B)), and hence closed. Consequently, {1, −1} would be an open set, in violation of (A). Sixth Proof. Our final proof goes a considerable step further and demonstrates not only that there are infinitely many primes, but also that the series p∈P 1 p diverges. The first proof of this important result was given by Euler (and is interesting in its own right), but our proof, devised by Erdos, is of compelling beauty. ˝ Let p1, p2, p3,... be the sequence of primes in increasing order, and assume that p∈P 1 p converges. Then there must be a natural number k such that i≥k+1 1 pi < 1 2 . Let us call p1,...,pk the small primes, and pk+1, pk+2,... the big primes. For an arbitrary natural number N we therefore find i≥k+1 N pi < N 2 . (1)
6 Six proofs of the infinity of primes Let N be the number of positive integers nN which are divisible by at least one big prime,and Ns the number of positive integers nN which have only small prime divisors.We are going to show that for a suitable N Nb+N。<N, which will be our desired contradiction,since by definition N+N.would have to be equal to N. To estimate N note that counts the positive integers nN which are multiples of pi.Hence by (1)we obtain (2) >k+1 Let us now look at N.We write every nN which has only small prime divisors in the form n=ab,where an is the square-free part.Every an is thus a product of different small primes,and we conclude that there are precisely2 different square---free parts..Furthermore,.asbn≤√元≤√F, we find that there are at most vN different square parts,and so Ns≤2kVN Since (2)holds for any N,it remains to find a number N withN or1VN,and for this N =22k+2 will do. ☐ Appendix:Infinitely many more proofs Our collection of proofs for the infinitude of primes contains several other old and new treasures,but there is one of very recent vintage that is quite different and deserves special mention.Let us try to identify sequences S of integers such that the set of primes Ps that divide some member of S is infinite.Every such sequence would then provide its own proof for the infinity of primes.The Fermat numbers Fn studied in the second proof form such a sequence,while the powers of 2 don't.Many more examples are provided by a theorem of Issai Schur,who showed in 1912 that for every nonconstant polynomial p(x)with integer coefficients the set of all nonzero values{p(n)≠0：n∈N}is such a sequence..For the polynomial p(x)=z,Schur's result gives us Euclid's theorem.As another example, forp(x）=x2+1 we get that the“squares plus one”contain infinitely many different prime factors. The following result due to Christian Elsholtz is a real gem:It generalizes Schur's theorem,the proof is just clever counting,and it is in a certain sense Issai Schur best possible
6 Six proofs of the infinity of primes Let Nb be the number of positive integers n ≤ N which are divisible by at least one big prime, and Ns the number of positive integers n ≤ N which have only small prime divisors. We are going to show that for a suitable N Nb + Ns < N, which will be our desired contradiction, since by definition Nb + Ns would have to be equal to N. To estimate Nb note that N pi counts the positive integers n ≤ N which are multiples of pi. Hence by (1) we obtain Nb ≤ i≥k+1 N pi < N 2 . (2) Let us now look at Ns. We write every n ≤ N which has only small prime divisors in the form n = anb2 n, where an is the square-free part. Every an is thus a product of different small primes, and we conclude that there are precisely 2k different square-free parts. Furthermore, as bn ≤ √n ≤ √ N, we find that there are at most √ N different square parts, and so Ns ≤ 2k √ N. Since (2) holds for any N, it remains to find a number N with 2k √ N ≤ N 2 or 2k+1 ≤ √ N, and for this N = 22k+2 will do. Appendix: Infinitely many more proofs Our collection of proofs for the infinitude of primes contains several other old and new treasures, but there is one of very recent vintage that is quite different and deserves special mention. Let us try to identify sequences S of integers such that the set of primes PS that divide some member of S is infinite. Every such sequence would then provide its own proof for the infinity of primes. The Fermat numbers Fn studied in the second proof form such a sequence, while the powers of 2 don’t. Many more examples Issai Schur are provided by a theorem of Issai Schur, who showed in 1912 that for every nonconstant polynomial p(x) with integer coefficients the set of all nonzero values {p(n) =0: n ∈ N} is such a sequence. For the polynomial p(x) = x, Schur’s result gives us Euclid’s theorem. As another example, for p(x) = x2 + 1 we get that the “squares plus one” contain infinitely many different prime factors. The following result due to Christian Elsholtz is a real gem: It generalizes Schur’s theorem, the proof is just clever counting, and it is in a certain sense best possible.