Using the Bertrand’s Postulate

The Bertrand’s Postulate is one useful fact that allows a simple proof to very nice theorems. It’s named after the french mathematician Joseph Bertrand, not the british Bertrand Russell. Being verified for numbers less than 3 million by Joseph Bertrand, it became a theorem after a proof by Pafnuty Chebyshev, followed by many different proofs by Ramanujan, Erdös and others. Enought history for now. It’s assertion can be simply stated as:

(Bertrand Postulate / Bertrand-Chevyshev Theorem)
For every n > 1 there is at least one prime p such that n < p < 2n.

There are relatively simple and elementary proofs for this theorem, but it’ll be the theme of another post. Let’s focus now on some consequences of this fact.


Let’s now change a little the assertion an say that for n \geq 3, there is always a prime p such that \frac{n}{2} < p < n. In fact, for even n = 2k, we have a prime p such k < p < 2k for k > 1, so there is a prime in \frac{n}{2} < p < n for n > 2. For odd n = 2k - 1, we have a prime p such k < p < 2k for k > 1, so there is a prime in \frac{n}{2} + \frac{1}{2} < p < n + 1, but n + 1 is even > 2, therefore n+1 is not a prime, so p lies in \frac{n}{2} < p < n \blacksquare.

Now let’s try some interesting propositions:

Every positive integer can be written as the sum of distinct primes and the number 1.

Let’s use strong induction for this one. We know that this is true for n = 1 and n = 2. Let’s assume that for every n < k, one can write n as a sum of distinct primes or 1. For n = k \geq 3, by the Bertrand’s Postulate, there is a prime \frac{n}{2} < p < n, so we can write n = p + r. So by the induction hypothesis, r can be written as a sum of distinct primes, none of which can be p, as r < p, ending the proof \blacksquare.

For all n > 1, there exists a prime p such \nu_p(n!) = 1.

Where \nu_p(a) is the exponent of the prime p in the factorization of a. Read this for more details. We are arguing that there is always a prime that appears only once in the factorization of n!. For n=2, we know that \nu_2(2!) = 1. By the Bertrand’s Postulate, for n > 2, there is a prime p such \frac{n}{2} < p < n, implying 2p > n, so p appears in n! and 2p does not. Therefore, \nu_p(n!) = 1 \blacksquare.

For n>1, \sqrt{n!} is not an integer.

Using the proposition above, it is clear that as \nu_p(n!) = 1, \sqrt{n!} can’t be an integer. In fact, \sqrt{a} \in \mathbb{Z} implies that \nu_p(a) \equiv 0 (\text{mod } 2) for all prime p, which is not the case. The same reasoning applies to \sqrt[k]{n!}, which would be an integer if \nu_p(n!) \equiv 0 (\text{mod } k) for all prime p, but there is at least one such \nu_p(n!) = 1 \blacksquare.

Let \mathcal{H}_n be the n-th Harmonic number, that is:

    \[ \mathcal{H}_n = \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n} \]

If n > 1, then \mathcal{H}_n is not an integer.

We know that \lim_{n \rightarrow \infty} \mathcal{H}_n = \infty, we argue that it never hits another integer after n=1. In this case, the Bertrand’s Postulate don’t seem useful here. Let’s use the auxiliary fact above. If \mathcal{H}_n is an integer, then the following number is an integer.

    \[ n!\mathcal{H}_n = \sum_{k=1}^{n}\frac{n!}{k}\]

But there is some p < n such \nu_p(n!) = 1, which means that if k \neq p, then p divides \frac{n!}{k}, but doesn’t divides \frac{n!}{p}. Therefore, the lefthand side of the equation is divisible by p, and also all the terms on the righthand side, except one, absurd \blacksquare.

Leave a Reply