{"history":[],"article":{"id":"dc1ad535-9b08-44c9-9f19-5656472a9fc5","title":"Proof of Bertrand's postulate","slug":"proof-of-bertrand-s-postulate","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), [Bertrand's postulate](https://bliptext.com/articles/bertrand-s-postulate) (now a [theorem](https://bliptext.com/articles/theorem)) states that, for each n \\ge 2, there is a [prime](https://bliptext.com/articles/prime-number) p such that n0, we have\n**Proof:** Applying the [binomial theorem](https://bliptext.com/articles/binomial-theorem),\nsince is the largest term in the sum in the right-hand side, and the sum has 2n terms (including the initial 2 outside the summation).\n\n## Lemma 2\nFor a fixed prime p, define R = R(n,p) to be the p-adic order of, that is, the largest [natural number](https://bliptext.com/articles/natural-number) r such that p^r divides.\nFor any prime p,.\n**Proof:** The exponent of p in n! is given by [Legendre's formula](https://bliptext.com/articles/legendre-s-formula)\nso\nBut each term of the last summation must be either zero (if ) or one (if ), and all terms with are zero.\nTherefore,\nand\n\n## Lemma 3\nIf p is an [odd](https://bliptext.com/articles/parity-mathematics) prime and, then R(n,p) = 0.\n**Proof:** There are exactly two factors of p in the numerator of the expression, coming from the two terms p and 2p in (2n)!, and also two factors of p in the denominator from one copy of the term p in each of the two factors of n!.\nThese factors all cancel, leaving no factors of p in.\n(The bound on p in the preconditions of the lemma ensures that 3p is too large to be a term of the numerator, and the assumption that p is odd is needed to ensure that 2p contributes only one factor of p to the numerator.)\n\n## Lemma 4\nAn upper bound is supplied for the [primorial](https://bliptext.com/articles/primorial) function,\nwhere the product is taken over all prime numbers p less than or equal to n.\nFor all n\\ge1, n\\#<4^n.\n**Proof:** We use [complete induction](https://bliptext.com/articles/mathematical-induction).\nFor n=1,2 we have 1\\#=1<4 and.\nLet us assume that the inequality holds for all.\nSince n=2k>2 is composite, we have\nNow let us assume that the inequality holds for all 1\\le n\\le2k.\nSince is an integer and all the primes appear only in the numerator, we have\nTherefore,\n\n# Proof of Bertrand's Postulate\nAssume that there is a [counterexample](https://bliptext.com/articles/counterexample): an integer n ≥ 2 such that there is no prime p with n < p < 2n.\nIf 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 < 2n.\nTherefore, n ≥ 427.\nThere are no prime factors p of such that:\nTherefore, every prime factor p satisfies p ≤ 2n / 3.\nWhen the number has at most one factor of p.\nBy [Lemma 2](https://bliptext.com/articles/), for any prime p we have pR(p,n) ≤ 2n, and since 1 is neither prime nor composite.\nThen, starting with [Lemma 1](https://bliptext.com/articles/) and decomposing the right-hand side into its prime factorization, and finally using [Lemma 4](https://bliptext.com/articles/), these bounds give:\nTherefore\nTaking [logarithms](https://bliptext.com/articles/logarithm) yields\nBy [concavity](https://bliptext.com/articles/concave-function) of the right-hand side as a function of n, the last inequality is necessarily verified on an interval.\nSince it holds true for n=426 and it does not for n=427, we obtain\nBut these cases have already been settled, and we conclude that no counterexample to the postulate is possible.\n\n## Addendum to proof\nIt is possible to reduce the bound to n=50.\nFor n\\ge17, we get, so we can say that the product p^R is at most , which gives\nwhich is true for n=49 and false for n=50.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T18:54:40.573Z","updated_at":"2025-01-25T18:54:40.573Z","search_vector":"'bertrand':3 'postul':5 'proof':1","search_content":" \n \n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), [Bertrand's postulate](https://bliptext.com/articles/bertrand-s-postulate) (now a [theorem](https://bliptext.com/articles/theorem)) states that, for each n \\ge 2, there is a [prime](https://bliptext.com/articles/prime-number) p such that n 0, we have\n**Proof:** Applying the [binomial theorem](https://bliptext.com/articles/binomial-theorem),\nsince is the largest term in the sum in the right-hand side, and the sum has 2n terms (including the initial 2 outside the summation).\n\n## Lemma 2\nFor a fixed prime p, define R = R(n,p) to be the p-adic order of, that is, the largest [natural number](https://bliptext.com/articles/natural-number) r such that p^r divides.\nFor any prime p,.\n**Proof:** The exponent of p in n! is given by [Legendre's formula](https://bliptext.com/articles/legendre-s-formula)\nso\nBut each term of the last summation must be either zero (if ) or one (if ), and all terms with are zero.\nTherefore,\nand\n\n## Lemma 3\nIf p is an [odd](https://bliptext.com/articles/parity-mathematics) prime and, then R(n,p) = 0.\n**Proof:** There are exactly two factors of p in the numerator of the expression, coming from the two terms p and 2p in (2n)!, and also two factors of p in the denominator from one copy of the term p in each of the two factors of n!.\nThese factors all cancel, leaving no factors of p in.\n(The bound on p in the preconditions of the lemma ensures that 3p is too large to be a term of the numerator, and the assumption that p is odd is needed to ensure that 2p contributes only one factor of p to the numerator.)\n\n## Lemma 4\nAn upper bound is supplied for the [primorial](https://bliptext.com/articles/primorial) function,\nwhere the product is taken over all prime numbers p less than or equal to n.\nFor all n\\ge1, n\\# 2 is composite, we have\nNow let us assume that the inequality holds for all 1\\le n\\le2k.\nSince is an integer and all the primes appear only in the numerator, we have\nTherefore,\n\n# Proof of Bertrand's Postulate\nAssume that there is a [counterexample](https://bliptext.com/articles/counterexample): an integer n ≥ 2 such that there is no prime p with n < p < 2n.\nIf 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 < 2n.\nTherefore, n ≥ 427.\nThere are no prime factors p of such that:\nTherefore, every prime factor p satisfies p ≤ 2n / 3.\nWhen the number has at most one factor of p.\nBy [Lemma 2](https://bliptext.com/articles/), for any prime p we have pR(p,n) ≤ 2n, and since 1 is neither prime nor composite.\nThen, starting with [Lemma 1](https://bliptext.com/articles/) and decomposing the right-hand side into its prime factorization, and finally using [Lemma 4](https://bliptext.com/articles/), these bounds give:\nTherefore\nTaking [logarithms](https://bliptext.com/articles/logarithm) yields\nBy [concavity](https://bliptext.com/articles/concave-function) of the right-hand side as a function of n, the last inequality is necessarily verified on an interval.\nSince it holds true for n=426 and it does not for n=427, we obtain\nBut these cases have already been settled, and we conclude that no counterexample to the postulate is possible.\n\n## Addendum to proof\nIt is possible to reduce the bound to n=50.\nFor n\\ge17, we get, so we can say that the product p^R is at most , which gives\nwhich is true for n=49 and false for n=50.","revisionCount":0},"hasMore":false,"nextCursor":null}

History