Bertrand's Postulate Part 2: Restricting the Factor Domain

Click here to see part one of this four week series.



This is week two of a four week series on the proof to Bertrand's Postulate. Last week, I went over some history and definitions pertaining to the problem, as well as introducing some facts about Pascal's triangle that come into play in the proof. This week, we can begin the actual process of proving that there is always a prime between n and 2n.

The proof utilizes the central binomial coefficients that I explained last week, each one being written in the form "2n choose n." The final conclusion actually states that every number of the form "2n choose n" has a prime factor between n and 2n. By determining this, we will then be able to say that there must always then be a prime between n and 2n. But how do we prove that?

This week, we will look at how to limit the range of possible prime factors of "2n choose n." If there are fewer possibilities of where these factors can exist on the number line, then it will be tougher (and eventually impossible) to find a number of this form without a prime factor between n and 2n. Next week, we will set a lower and upper bound on the size of "2n choose n," which will provide an inequality to work with. And in the last post, we will show that because of all of these restraints, there must be a prime between n and 2n. So let's get to it!

The first step is to prove that none of the prime factors of “2n choose n” are between ⅔n and n. By proving this, it will restrict the amount of spots for the prime factor to exist, and hopefully at some point restricting it to between n and 2n.

To prove this, we first need to go over the definition of factorials.

The number n factorial (written n!) is the product of all of the positive integers less than or equal to n.

For example, 4! = 4 • 3 • 2 • 1 = 24. 7! = 7 • 6 • 5 • 4 • 3 • 2 • 1 = 5040.

How do factorials play into this proof? Well, assuming that the prime p is between ⅔n and n, p will only appear once in the prime factorization of n!. This is because n! only has prime factors that are less than n. For p to have been multiplied in twice, that means 2p also must be less than n. But, what happens when we multiply the inequality by two?

⅔n < p < n
2(⅔n) < 2p < 2n
1⅓n < 2p < 2n

This means that 2p is at least 1⅓n, which cannot be a factor of n!. So, a factor of p can only appear once. By similar logic, there are two factors of p in (2n)!.

A simpler way to write “number of times a prime factor appears in a number” would be to use the following notation:

v_p(x)

Assume that p is the prime number and x is the number that the prime is a factor of. For example:

v₂(24) = 3
v₅(50) = 2
v_p((2n)!) = 1
v_p((2n)!) = 2

There exists a formula that enables one to find the number of times a certain prime factor appears in the factorization of a quantity like “2n choose n.” For that example, the formula goes:

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)

The values of p or n are not defined (aside from the fact that p is between ⅔n and n), but we just determined the number of times p appeared in n! and (2n)! nonetheless. It appeared in n! once and (2n)! twice. So, those values can be substituted in to see how many p’s can be in “2n choose n.”

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)
v_p(“2n choose n”) = 2 - 2(1)
v_p(“2n choose n”) = 2 - 2
v_p(“2n choose n”) = 0

So, p appears zero times when it is between ⅔n and n. In other words, “2n choose n” has no prime factors between ⅔n and n, thus completing this part of the proof.

The second step is to prove that there are no prime factors of “2n choose n” that are greater than 2n. Furthermore, this step will also demonstrate that there are no powers of prime factors of “2n choose n” greater than 2n. This will continue the process of restricting possible prime factors of step one, which will later make it impossible to have no prime factors between n and 2n.

This step will require another definition, but this one is extremely simple. The name of it makes it sound much more complicated than it is.

A number’s floor function is the greatest integer less than or equal to that number. For example:

floor(7.5) = 7
floor(18) = 18
floor(π) = 3

These floor functions play a role in Legendre’s Theorem (created by Adrien-Marie Legendre), which is used in the proof of step two. Legendre’s Theorem states that to find the prime factorization of n!, one simply plugs prime numbers into the following formula, which will find their exponent.

v_p(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + floor(n/p⁴) + ...

For example, let’s find the exponent of 2 in the number 4! = 24.

v_p(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + floor(n/p⁴) + ...
v₂(4!) = floor(4/2) + floor(4/2²) + floor(4/2³) + floor(4/2⁴) + ...
v₂(4!) = floor(4/2) + floor(4/4) + floor(4/8) + floor(4/16) + ...
v₂(4!) = floor(2) + floor(1) + floor(0.5) + floor(0.25) + ...
v₂(4!) = 2 + 1 + 0 + 0 + ...
v₂(4!) = 3

Let’s return to the formula we used in the last step to find the exponent on a prime factor of “2n choose n.”

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)

It is impossible to use logic to define the exponent on primes greater than 2n for the terms in this formula. However, we can use Legendre’s Theorem to determine the exponent on prime factors of n! and (2n)!.

v_p(“2n choose n”) = v_p((2n)!) - 2v_p(n!)
v_p(“2n choose n”) = [floor(2n/p) + floor(2n/p²) + ...] - 2[floor(n/p) + floor(n/p²) + ...]

Though 2n cannot be plugged in for p (2n is even, and therefore is not prime), but any number larger than 2n can be plugged in to see if it has a non-zero exponent. But, the first term in each of the two infinite series will end up as zero (2n divided by a number larger than 2n is less than one, and thus, will have a floor function of zero). Since each term in each series is shrinking, they will all end up with a floor function of zero. So, both infinite sums will simplify to zero.

v_p(“2n choose n”) = 0 - 2(0)
v_p(“2n choose n”) = 0 - 0
v_p(“2n choose n”) = 0

So, all p values greater than 2n will have an exponent of zero, meaning that there are no prime factors of “2n choose n” greater than 2n. This completes the second step.

Make sure to return next week so we can start to restrain the size of the number "2n choose n," and then we will be just inches away from the proof of Bertrand's Postulate.