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 there is at least one prime such that .
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 , there is always a prime such that . In fact, for even , we have a prime such for , so there is a prime in for . For odd , we have a prime such for , so there is a prime in , but is even , therefore is not a prime, so lies in .
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 and . Let’s assume that for every , one can write as a sum of distinct primes or 1. For , by the Bertrand’s Postulate, there is a prime , so we can write . So by the induction hypothesis, can be written as a sum of distinct primes, none of which can be , as , ending the proof .
For all , there exists a prime such .
Where is the exponent of the prime in the factorization of . Read this for more details. We are arguing that there is always a prime that appears only once in the factorization of . For , we know that . By the Bertrand’s Postulate, for , there is a prime such , implying , so appears in and does not. Therefore, .
For , is not an integer.
Using the proposition above, it is clear that as , can’t be an integer. In fact, implies that for all prime , which is not the case. The same reasoning applies to , which would be an integer if for all prime , but there is at least one such .
Let be the n-th Harmonic number, that is:
If , then is not an integer.
We know that , we argue that it never hits another integer after . In this case, the Bertrand’s Postulate don’t seem useful here. Let’s use the auxiliary fact above. If is an integer, then the following number is an integer.
But there is some such , which means that if , then divides , but doesn’t divides . Therefore, the lefthand side of the equation is divisible by , and also all the terms on the righthand side, except one, absurd .