Solved prime-number problem
In mathematics, Bertrand's postulate (now a theorem) states that, for each formula_1, there is a prime formula_2 such that formula_3 in order to be large enough. This is achieved through analysis of their factorizations.
The main steps of the proof are as follows. First, one shows that the contribution of every prime power factor formula_4 in the prime decomposition of the central binomial coefficient formula_5 is at most formula_6; then, one shows that every prime larger than formula_7 appears at most once.
The next step is to prove that formula_8 has no prime factors in the interval formula_9. As a consequence of these bounds, the contribution to the size of formula_8 coming from the prime factors that are at most formula_11 grows asymptotically as formula_12 for some formula_13. Since the asymptotic growth of the central binomial coefficient is at least formula_14, the conclusion is that, by contradiction and for large enough formula_11, the binomial coefficient must have another prime factor, which can only lie between formula_11 and formula_6.
The argument given is valid for all formula_18. The remaining values of formula_11 are verified by direct inspection, which completes the proof.
Lemmas in the proof.
The proof uses the following four lemmas to establish facts about the primes present in the central binomial coefficients.
Lemma 1.
For any integer formula_20, we have
formula_21
Proof: Applying the binomial theorem,
formula_22
since formula_8 is the largest term in the sum in the right-hand side, and the sum has formula_6 terms (including the initial formula_25 outside the summation).
Lemma 2.
For a fixed prime formula_2, define formula_27 to be the "p"-adic order of formula_8, that is, the largest natural number formula_29 such that formula_4 divides formula_8.
For any prime formula_2, formula_33.
Proof: The exponent of formula_2 in formula_35 is given by Legendre's formula
formula_36
so
formula_37
But each term of the last summation must be either zero (if formula_38) or one (if formula_39), and all terms with formula_40 are zero. Therefore,
formula_41
and
formula_42
Lemma 3.
If formula_2 is an odd prime and formula_44, then formula_45
Proof: There are exactly two factors of formula_2 in the numerator of the expression formula_47, coming from the two terms formula_2 and formula_49 in formula_50, and also two factors of formula_2 in the denominator from one copy of the term formula_2 in each of the two factors of formula_35. These factors all cancel, leaving no factors of formula_2 in formula_8. (The bound on formula_2 in the preconditions of the lemma ensures that formula_57 is too large to be a term of the numerator, and the assumption that formula_2 is odd is needed to ensure that formula_49 contributes only one factor of formula_2 to the numerator.)
Lemma 4.
An upper bound is supplied for the primorial function,
formula_61
where the product is taken over all "prime" numbers formula_2 less than or equal to formula_11.
For all formula_64, formula_65.
Proof: We use complete induction.
For formula_66 we have formula_67 and formula_68.
Let us assume that the inequality holds for all formula_69. Since formula_70 is composite, we have
formula_71
Now let us assume that the inequality holds for all formula_72. Since formula_73 is an integer and all the primes formula_74 appear only in the numerator, we have
formula_75
Therefore,
formula_76
Proof of Bertrand's Postulate.
Assume that there is a counterexample: an integer "n" ≥ 2 such that there is no prime "p" with "n"  ; "p"  ; 2"n".
If 2 ≤ "n" ; 427, then "p" can be chosen from among the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (each being the largest prime less than twice its predecessor) such that "n"  ; "p"  ; 2"n". Therefore, "n" ≥ 427.
There are no prime factors "p" of formula_77 such that:
Therefore, every prime factor "p" satisfies "p" ≤ 2"n"&amp;hairsp;/&amp;hairsp;3.
When formula_78 the number formula_79 has at most one factor of "p". By Lemma 2, for any prime "p" we have "p""R"("p","n") ≤ 2"n", and formula_80 since 1 is neither prime nor composite. Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, and finally using Lemma 4, these bounds give:
formula_81
Therefore
formula_82, which simplifies to formula_83
Taking logarithms yields
formula_84
By concavity of the right-hand side as a function of "n", the last inequality is necessarily verified on an interval. Since it holds true for formula_85 and it does not for formula_86, we obtain
formula_87
But these cases have already been settled, and we conclude that no counterexample to the postulate is possible.
Addendum to proof.
It is possible to reduce the bound to formula_88.
For formula_89 we get formula_90, so we can say that the product formula_91 is at most formula_92, which gives
formula_93
which is true for formula_94 and false for formula_88.
References.
 ;templatestyles src="Reflist/styles.css" / ;