Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving (a weaker form of) Bertrand's postulate

  1. Jan 4, 2012 #1
    It is known that for every n > 1 there is always at least one prime p such that n < p < 2n.

    The Bertrand's theorem's proof I read is quite involved. I've thought of another way to prove it but I think it's too simple to be correct. Can anyone please point out my mistakes?

    below, Fundamental Theorem means the Fundamental Theorem of Arithmetic

    Proof:
    #
    1) for any n > 1, n can be expressed as a product of prime factors (Fundamental Theorem)
    2) Let PF[n] be a set containing all prime numbers that appear in the prime factorization of n.
    e.g. PF[6] = {2,3}
    3) obviously, if x is in PF[n] then x ≤ n.
    4) for all prime numbers that are smaller than n, we look for one that is not in PF[n], if it exists, let it be M.

    for M exists:
    5a) consider K = n + M, K ≤ 2n (from 4)
    6a) now, K is not divisible by any prime smaller than n, since for any prime that divides n, it does not divide M, and M does not divide n. (from 4)
    7a) but K has a prime factorization (Fundamental Theorem)
    8a) hence there must be a prime in the range [n, 2n]

    for M not exists:
    5b) consider K' = n+1, K ≤ 2n (assumption, n>1)
    6b) now, K is not divisible by any prime smaller than n, since for any prime that divides n, it does not divide 1.
    7b) but K has a prime factorization (Fundamental Theorem)
    8b) hence there must be a prime in the range [n, 2n]

    This proof seems alright to me, but after all I'm just an amateur. I would be grateful if anyone could point out the insufficiency of this proof so that I can learn from my mistakes.

    Thanks.
     
    Last edited: Jan 4, 2012
  2. jcsd
  3. Jan 4, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I think it's not hard to show that M will always exist. For n somewhat large.

    Problem: What if K=2n?? Then you indeed found a prime in [n,2n], but a prime that equals n. Bertrand's postulate says that it must be STRICTLY larger than n!!

    This is not true. Take n=8, take M=7. Then K=15 is divisible by 5 and 3 which are both smaller than n.
     
  4. Jan 4, 2012 #3
    ok, I understand now, thanks!
     
  5. Jan 6, 2012 #4
    For any [itex]k\geq 2[/itex] choose [itex]n[/itex] to be the product of all prime numbers [itex]\leq k.[/itex] Then [itex]\{p\in\mathbb{P} : p < n, p \not |n \}=\emptyset.[/itex] So [itex]M[/itex] need not exist, if I'm not mistaken.
     
  6. Jan 6, 2012 #5
    The problem here is, that you use the fact that if [itex]p|(n+M) \text{ and } p|n \Rightarrow p|M.[/itex] But this doesn't cover all the possibilities, namely if [itex]p\not|n \text{ and } p\not|M \text{ but } p|(n+M),[/itex] as micromass pointed out.
     
  7. Jan 6, 2012 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Not true. Take k=10. Then n=2*3*5*7=210. There are a lot of primes smaller than 210.
     
  8. Jan 6, 2012 #7
    woops, sorry, got mixed up with my thoughts, you're right.
     
  9. Feb 4, 2012 #8
    Erdos has a very elegant proof of this theorem.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving (a weaker form of) Bertrand's postulate
  1. Prove it (Replies: 6)

  2. Proves that (Replies: 3)

  3. Prove This (Replies: 1)

  4. Forms and determinants (Replies: 1)

Loading...