Take the 2-minute tour ×
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.

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$.(I'm a little shaky about this part of the proof).

Can anyone spot an error, or has anyone seen this proof before?

share|improve this question
    
Which problem in Dummit and Foote needs Bertrand's postulate? –  lhf May 24 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 at 15:36

2 Answers 2

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|improve this answer
1  
Ok that's what the problem was! Thank you. –  Robearz May 24 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|improve this answer
    
Oops you were right. Thanks for the help. –  Robearz May 24 at 12:44

Your Answer

 
discard

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.