Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Proof of Bertrand's postulate

In mathematics, Bertrand's postulate states that for each n ≥ 2 there is a prime p such that n < p < 2n. It was first proven by Pafnuty Chebyshev; the gist of the following elementary but involved proof by contradiction is due to Paul Erdös.

We denote the set of prime numbers with and define:

Lemma

Proof

n = 1:

n = 2:

n > 2 and n is even:

(by induction)

(because every even no. is not prime, so the sum is aligned with the previous prime)

and n is odd. Let n = 2m+1 with m > 0:

Each prime p with divides giving us:

By induction , so:

Q.E.D.

Now for the proof of Bertrand's postulate. Assume there is a counterexample: an integer n ≥ 2 such that there is no prime p with n < p < 2n.

If 2 ≤ n < 2048, then one of the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503 (each being less than twice its predecessor), call it p, will satisfy n < p < 2n. Therefore n ≥ 2048.

Since is the largest term in the sum we have:

Define to be highest number x, such that divides . Since n !Number theory Combinatorics In mathematics, the factorial of a natural number n is the product of the positive integers less than or equal to n''. This is written as n and pronounced n factorial". The notation n was introduced by Christian Kramp in 1808. has factors of p we get:

Since each term can either be 0 or 1 and all terms with are 0 we get:

For we have or .

has no prime factors p such that:

2n < p, because 2n is the largest factor.
, because of a trivialThe word trivial has several common uses: # Something that anyone can understand and explain to others — as opposed to something sublime, transcendental, etc. or simply difficult''. Of little significance or value. Ordinary; commonplace; trifling; vulgar. expansion of the original assumption.
, because (since ) which gives us .

Each prime factor of is therefore not larger than .

has at most one factor of every prime . As , the productIn mathematics, a product is the result of multiplying, or an expression that identifies factors to be multiplied. The order in which real or complex numbers are multiplied has no bearing on the product; this is known as the commutative law of multiplicat of over all other primes is at most . Since is the product of over all primes p, we get:

Using our lemma :

Since we have :

Also (since ):

Taking logarithmsIn mathematics, the logarithm functions are the inverses of the exponential functions. Logarithms are numbers that are substituted in computation for other numbers, to which they bear such a relation that the operations to be performed on the latter are r:

Substituting 2^2t for 2n:

This gives us t < 6 and the contradiction:

Thus no counterexample to the postulate is possible.

Q.E.D.

Politics	Business	Finance

Topics: Proof Of Bertrand's Postulate Prime Q.e.d Induction...

ProofThe word proof can mean: originally, a test assessing the validity or quality of something. a rigorous, compelling argument, including: a logical argument or a mathematical proof (see also proof theory). a legal proof. a large accumulation of scientific e	Proofs of Fermat's little theoremThis is a collection of proofs of Fermat's little theorem: a p a ( mod p for every prime number p and every integer a''. Note that it is enough to prove a p − 1 1 (mod p for every integer a which is relatively prime to p (i. not a multiple of p .	Proof of angular momentumA proof that torque is equal to the time- derivative of angular momentum can be stated as follows: The definition of angular momentum for a single particle is: where "×" indicates the vector cross product. The time-derivative of this is: d L ''dt r × d p
Proof (play)Proof is a play by David Auburn which won the 2001 Pulitzer Prize for Drama and the 2001 Tony Award for Best Play. It concerns the daughter of a recently-deceased professor of mathematics at the University of Chicago and her struggle with mathematical gen	Proof theoryLogic Proof theory Proof theory studied as a branch of mathematical logic, represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures, suc	Proof of mathematical inductionThe principle of mathematical induction can be proved if the following axiom is assumed: :The set of all natural numbers is well-ordered (that is, every non-empty set of natural numbers has a least element). A simplified version is given here. This proof
Proofreading	Proof that the sum of the reciprocals of the primes diverges	Proof of Bertrand's postulate
Proof that e is irrational	Proof by exhaustion	Proof coinage
Proof that holomorphic functions are analytic	Proof of concept	Proofs and Refutations

Non User