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.

Consequences

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