Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.