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 2014Six 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 Leon￾hard 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