10 Bertrand's postulate (2)Next we prove that Πp≤4- for all realx≥2， (1) . p≤x m叶以 where our notation-here and in the following-is meant to imply that 陈 the product is taken over all prime numbers p x.The proof that we present for this fact uses induction on the number of these primes.It is 1 not from Erdos'original paper,but it is also due to Erdos(see the margin). and it is a true Book Proof.First we note that if g is the largest prime with m2s乙m1 g≤x,then 1<领Π次 Πp=Πpand 49-1≤4r-1. p≤x Thus it suffices to check(1)for the case where z=g is a prime number.For q=2 we get“2≤4，”so we proceed to consider odd primes q=2m+1. (Here we may assume,by induction,that(1)is valid for all integers x in the set {2,3,...,2m}.)For g=2m +1 we split the product and compute g≤("） 4m22m=42m All the pieces of this"one-line computation"are easy to see.In fact, Πp≤4m p≤m+1 holds by induction.The inequality Π p≤ 2m+1 m m+1<p≤2m+1 follows from the observation that ()is an integer.where the primes that we consider all are factors of the numerator(2m +1)!,but not of the denominator m!(m +1)!.Finally Legendre's theorem ≤22m The number n!contains the prime holds since factor p exactly are two (equal!)summands that appear in times. Proof.Exactly of the factors m+1 of n!=1.2.3...n are divisible by 9- p.which accounts for p-factors. Next,L÷」of the factors of nare (3)From Legendre's theorem(see the box)we get that (con- even divisible by p2,which accounts tains the prime factor p exactly for the next÷」prime factors p of n!,etc. ◇ (-)10 Bertrand’s postulate (2) Next we prove that p≤x p ≤ 4x−1 for all real x ≥ 2, (1) where our notation — here and in the following — is meant to imply that the product is taken over all prime numbers p ≤ x. The proof that we present for this fact uses induction on the number of these primes. It is not from Erdos’ original paper, but it is also due to Erd ˝ os (see the margin), ˝ and it is a true Book Proof. First we note that if q is the largest prime with q ≤ x, then p≤x p = p≤q p and 4q−1 ≤ 4x−1. Thus it suffices to check (1) for the case where x = q is a prime number. For q = 2 we get “2 ≤ 4,” so we proceed to consider odd primes q = 2m + 1. (Here we may assume, by induction, that (1) is valid for all integers x in the set {2, 3,..., 2m}.) For q = 2m + 1 we split the product and compute p≤2m+1 p = p≤m+1 p · m+1<p≤2m+1 p ≤ 4m 2m + 1 m  ≤ 4m22m = 42m. All the pieces of this “one-line computation” are easy to see. In fact, p≤m+1 p ≤ 4m holds by induction. The inequality m+1<p≤2m+1 p ≤ 2m + 1 m  follows from the observation that 2m+1 m  = (2m+1)! m!(m+1)! is an integer, where the primes that we consider all are factors of the numerator (2m + 1)!, but not of the denominator m!(m + 1)!. Finally 2m + 1 m  ≤ 22m holds since 2m + 1 m  and 2m + 1 m + 1  Legendre’s theorem The number n! contains the prime factor p exactly k≥1  n pk  times. Proof. Exactly  n p  of the factors of n!=1 · 2 · 3 ··· n are divisible by p, which accounts for  n p  p-factors. Next,  n p2  of the factors of n! are even divisible by p2, which accounts for the next  n p2  prime factors p of n!, etc. are two (equal!) summands that appear in 2 m+1 k=0  2m + 1 k  = 22m+1. (3) From Legendre’s theorem (see the box) we get that 2n n  = (2n)! n!n! con￾tains the prime factor p exactly  k≥1 2n pk  − 2  n pk