# A (possibly) easier version of Bertrand's Postulate

While attending a math puzzle contest, my friend (a math student) asked me to prove that $$\sum_{k=1}^n \frac{1}{k} \notin \mathbb{Z} \quad \forall n \geq 2$$

Being the first time seeing this problem, I came up with a proof that required the following conjecture:

(1) Given a composite number $n \geq 4$, $\exists p$ prime such that $$p < n < 2p$$

My friend told me that this followed directly from Bertrand's Postulate (and it indeed does).

Now Bertrand's postulate, which says that there exists a prime between $n$ and $2n$, has a pretty involved proof. My question is:

Question: Is there a simpler proof of Bertrand's Postulate if we take $n$ to be prime (which is all I need)? If so could someone either provide a reference or proof/sketch for the same? So far I have come up empty...

PS: Here is how I link (1) with Bertrand's Postulate: Define for composite $n \geq 4$ $$p(n) = \max \{p : p \leq n, \quad p \mbox{ prime} \}$$ Suppose (1) is wrong, then for some $n$, we have $$2p(n) \leq n$$ This also means that $\{p(n)+1, \cdots 2p(n)\}$ are all composite. However by Bertrand's Postulate, between $p(n)$ and $2p(n)$, there is a prime $q$. $\Rightarrow\Leftarrow$

• I suppose you are aware that $\sum_{k=1}^n \frac{1}{k} \notin \mathbb{Z} \quad \forall n \geq 2$ has a (well-known) simpler proof, by looking modulo powers of $2$ – Ewan Delanoy Apr 9 '14 at 5:53
• @Ewan: Yes I am. That was the proof my friend expected. However I needed to give some background on how I encountered this problem. – Gautam Shenoy Apr 9 '14 at 5:55

I just realized that proving the result for $n$ prime implies proving it for all $n \geq 4$. Here is my reasoning:
Let $p(n)$ be as before i.e. the prime number closest to $n$ and less than $n$. Then IF there was a simpler proof of Bertrand postulate for primes, then there exists a prime number $q$ between $p(n)$ and $2p(n)$. There are $2$ cases: $$p(n)<q<n<2p(n)<2n$$ and $$p(n)<n<q<2p(n)<2n$$
So if there is a simple(r) proof of Bertrand postulate for primes, the above argument extends it to $n \geq 4$. Hence it is "unlikely" for there to be a simple proof for the primes case since Erdos' proof is considered to be the simplest one as of now.