4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Which problem in Dummit and Foote needs Bertrand's postulate? $\endgroup$ – lhf May 24 '14 at 13:23
  • $\begingroup$ 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) $\endgroup$ – vonbrand May 24 '14 at 15:36
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Ok that's what the problem was! Thank you. $\endgroup$ – Robearz May 24 '14 at 12:29
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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