Bertrand's postulate Chapter 2 We have seen that the sequence of prime numbers 2,3,5,7,...is infinite. To see that the size of its gaps is not bounded,let N:=2.3.5...p denote the product of all prime numbers that are smaller than k+2,and note that none of the k numbers N+2,N+3,N+4,..,N+k,N+(k+1) is prime,since for 2 <i<k+1 we know that i has a prime factor that is smaller than k +2,and this factor also divides N,and hence also N+i. With this recipe,we find,for example,for k =10 that none of the ten numbers 2312,2313,2314,..,2321 is prime. But there are also upper bounds for the gaps in the sequence of prime num- bers.A famous bound states that"the gap to the next prime cannot be larger than the number we start our search at."This is known as Bertrand's pos- tulate,since it was conjectured and verified empirically for n 3 000000 by Joseph Bertrand.It was first proved for all n by Pafnuty Chebyshev in 1850.A much simpler proof was given by the Indian genius Ramanujan. Joseph Bertrand Our Book Proof is by Paul Erdos:it is taken from Erdos'first published paper,which appeared in 1932,when Erdos was 19. Bertrand's postulate Beweis eines Satzes von Tschebyschef For every n 1,there is some prime number p with n<p 2n. Veo尺Edie Budapes dessen es awischen einer maturlichen Zal und ihrer nweifachem stts wenigatens eine Priezan gibt,liegen in der Literatur mchrese Beweise vor.Als eintachsten kann man ohee Zwrael den Reweis von RAMANJAN)hereichoen.In seinem Werk Varlesungen fber Proof.We will estimate the size of the binomial coefficient(care- Zahlemtheorie (Leiprig.1927).Band I,S.66-68 gibt Herr LANDAD einen betonders einfachen Beweis fuir einen Satz uber die Anzahl fully enough to see that if it didn't have any prime factors in the range der Primzanlen unter einer gegebenen Grenze,aus welchem un- mitsibar olgt.da gtcigneles g awischen einer eatrlichem n<p≤2n,then it would be“too small..”Our argument is in five steps. (1)We first prove Bertrand's postulate for n 511.For this one does not f need to check 511 cases:it suffices (this is "Landau's trick")to check that g der dem LANDAUsche印Bewe山unde liegen tchen Satzes telangen ksen,der wie mir scheint-an Ein- nchkeit picht hinter dea HAMAnschen Beweis steht.(iriechische 2,3,5,7,13,23,43,83,163,317,521 luchstben sollen im Folgenden durclwegs positive.lateinische Buchstabem nattrliche Zahten bezcichren:dle Berelchnung p ist far Primaahlen vorbehalten. 1.Der Binomialkocthizient is a sequence of prime numbers,where each is smaller than twice the pre- vious one.Hence every interval fy n<y<2n),with n 511,contains -器 one of these 11 primes. M.Aigner,G.M.Ziegler,Proofs from THE BOOK,DOI 10.1007/978-3-662-44205-0_2, @Springer-Verlag Berlin Heidelberg 2014Bertrand’s postulate Chapter 2 Joseph Bertrand We have seen that the sequence of prime numbers 2, 3, 5, 7,... is infinite. To see that the size of its gaps is not bounded, let N := 2 · 3 · 5 ··· p denote the product of all prime numbers that are smaller than k + 2, and note that none of the k numbers N + 2, N + 3, N + 4,...,N + k, N + (k + 1) is prime, since for 2 ≤ i ≤ k + 1 we know that i has a prime factor that is smaller than k + 2, and this factor also divides N, and hence also N + i. With this recipe, we find, for example, for k = 10 that none of the ten numbers 2312, 2313, 2314,..., 2321 is prime. But there are also upper bounds for the gaps in the sequence of prime num￾bers. A famous bound states that “the gap to the next prime cannot be larger than the number we start our search at.” This is known as Bertrand’s pos￾tulate, since it was conjectured and verified empirically for n < 3 000 000 by Joseph Bertrand. It was first proved for all n by Pafnuty Chebyshev in 1850. A much simpler proof was given by the Indian genius Ramanujan. Our Book Proof is by Paul Erdos: it is taken from Erd ˝ os’ first published ˝ paper, which appeared in 1932, when Erdos was 19. ˝ Bertrand’s postulate For every n ≥ 1, there is some prime number p with n<p ≤ 2n. Proof. We will estimate the size of the binomial coefficient 2n n  care￾fully enough to see that if it didn’t have any prime factors in the range n<p ≤ 2n, then it would be “too small.” Our argument is in five steps. (1) We first prove Bertrand’s postulate for n ≤ 511. For this one does not need to check 511 cases: it suffices (this is “Landau’s trick”) to check that 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 521 is a sequence of prime numbers, where each is smaller than twice the pre￾vious one. Hence every interval {y : n<y ≤ 2n}, with n ≤ 511, contains one of these 11 primes. M. Aigner, G.M. Ziegler, Proofs from THE BOOK, DOI 10.1007/978-3-662-44205-0_2, © Springer-Verlag Berlin Heidelberg 2014