# Elementary Proof of Bertrand's Postulate? (Proof Check)

I was working on a problem in Dummit and Foote which had to do with Euler's totient function and I ended up needing to use Bertrand's postulate for my solution. I've never seen a proof for it, so I tried to prove it myself. I finally came up with a proof, but when I went to check out other proofs I didn't see mine and the ones I saw were much more involved, leading me to believe my proof is incorrect. However, after checking it multiple times I still can't find an error. Any input would be appreciated.

BP: For all $n\geq 3$ there exists a prime $p$ with $n<p<2n$

Proof. Suppose for some $n\geq3$, $n<l<2n$ implies that $l$ is composite. Let $A= \{2, ... , n-1 \}$ and $B=\{n+1, ..., 2n-1\}$ then $\left\vert{A}\right\vert= n-2$ and $\left\vert{B}\right\vert=n-1$. Consider the function $f: B\to A$ defined by $m \mapsto m/c$, where $c$ is the smallest prime dividing $m$. If $f$ is injective we have a contradiction.

Suppose $r=f(a)=f(b)$, by the FTOA $a=p_{1}^{\alpha_{1}}\cdot\ldots\cdot p_{k}^{\alpha_{k}}$ and $b=q_{1}^{\beta_{1}}\cdot\ldots\cdot q_{j}^{\beta_{j}}$ with $p_{1}<\cdots<p_{k}$ and $q_{1}<\cdots<q_{j}$ and then $f(a)=p_{1}^{\alpha_{1}-1}\cdot\ldots\cdot p_{k}^{\alpha_{k}}$ and $f(b)=q_{1}^{\beta_{1}-1}\cdot\ldots\cdot q_{j}^{\beta_{j}}$. The uniqueness of representation for $r$ by the FTOA implies that $p_{i} = q_{i}$ and $\alpha_{i} = \beta_{i}$ for all $i$, thus $a=b$.

Can anyone spot an error?

-
Which problem in Dummit and Foote needs Bertrand's postulate? – lhf May 24 '14 at 13:23
Erdös' first paper has a simple proof of Bertrand's postulate. It is also recorded in "Proofs from THE BOOK" (look it up in Wikipedia) – vonbrand May 24 '14 at 15:36

The problem is that you can't guarantee that $p_1=q_1$, because $\alpha_1-1$ or $\beta_1-1$ can be $0$. The unicity of the factorization assumes that the exponents are positive.

For instance: $$35=2^0\cdot5^1\cdot7^1=3^0\cdot5^1\cdot7^1$$ and this doesn't imply (fortunately) that $2=3$.

Any case, it is a very nice false proof.

-
Ok that's what the problem was! Thank you. – Robearz May 24 '14 at 12:29

The problem is in the last part. In fact, $f(11\cdot 13)=f(13^2)=13$ and $n<143<169<2n$ for $n=100$, for example.

All you can conclude about $a$ with $f(a)=r$ if you have $r$, is that $a=pr$ where $p$ is prime and $\le$ the smallest prime dividing $r$.

-