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

Proof about a prime between k and 2k.

  1. Apr 1, 2012 #1
    If K is a prime is there a prime between k and 2k.
    Obviously this is a weaker version of a prime between n and 2n that was proved by
    Erdos and Chebyshev.
    Lets assume that their isn't a prime between k and 2k.
    This would imply that all the numbers between k and 2k would have to be constructed
    from primes smaller than K. When I say constructed I mean their prime factorization.
    so there would have to be some product of primes that was in between
    k and 2k , [itex] k<P_1P_2....P_n<2k [/itex] with [itex] P_n<K [/itex]
    ok so as soon as we had one number in between k and 2k then the smallest prime that
    we could multiply it by is 2, but 2 times this product of primes would be bigger than 2k
    so we would not have constructed all the numbers between k and 2k.
    Actually I thought I could arrive at a contradiction but I lost my train of thought.
    any help would be much appreciated.
  2. jcsd
  3. Apr 2, 2012 #2
    While technically true, I would not say that the above statement for primes is any weaker than the more general statement for n>1.

    Bertrands postulate follows in fact immediately if you know that pi+1<2pi, where pi<pi+1 are two successive prime numbers.

    I doubt btw that anyone will find a simpler proof than the one by Erdös.
  4. Apr 4, 2012 #3
    ok here me out. We have to construct k numbers between k and 2k. with primes smaller than k. so we have [itex] \frac{k-1}{2} [/itex] choices of primes smaller than k to construct our numbers between k and 2k. Now if we use all the primes to construct a number in between k and 2k. then to construct another number we would be forced to use another prime at one point which would skip over 2k and it wouldn't work.
    because we have more numbers to construct than available primes we would eventually have to use another prime that would make us skip over 2k and this is a contradiction, therefore there is a prime between k and 2k. does this make sense or did i miss something.
  5. Apr 4, 2012 #4
  6. Apr 4, 2012 #5
    **** Not necessarily, imo. It could conceivably be that some of the integers between k and 2k are products of powers of primes already used before.."
    yes exactly.
    now lets say there is some integer Q that is between k and 2k. and
    we write it in its prime factorization. [itex] {P_1}^{x_1}{P_2}^{x_2}..... [/itex]
    now we know that this integer is in between k and 2k, now suppose we want to multiply Q by another prime to construct the other integers between k and 2k, ok so we do this and it can be a prime that is already used to construct Q, but even the smallest prime which is 2 will put us past 2k.
    So it is clear that I would have to multiply at least 2 primes less than
    k to get in between k and 2k. ok so I have these groups of 2 primes multiplied together to try to make all the numbers between k and 2k. Now I will eventually run out of unique primes to use so I will have to multiply some together to try to make the other ones, but if i do that i will skip past 2k. Does this make sense or am i missing something.
  7. Apr 5, 2012 #6

    I think you must be missing something but I can't tell anymore what exactly, after you seem either to reject my explanation or simply not address it at all.

    For example, if you take the prime k = 23, then 2k = 46 ==> we have to fill up k - 1 = 22 numbers between k and 2k, right? Now, there are at most (k-1)/2 = 11 primes less than k, and in fact there are only 8, and I can't see where you think you've proved that each and every integer between 24 and 45 (containing extremes) cannot be a product of these 8 (at most (k-1)/2) primes...

    You describe the situation when we already have a number between k and 2k and then "we want to multiply it by some prime", which of course would automatically take us beyond 2k, but what about having different product of those 8 primes there? For example, conceivably each number between k and 2k could be a product of two of these 8 primes, and since there are [itex]\binom{8}{2}=28[/itex] different pairs of such 8 primes we have more than enough to cover all the needed 22 numbers...

    Besides all the above, what Norwegian told you is plainly true: the general Betrand's Postulate follows at once from the claim you try to prove, so its proof would hardly be easier than the postulate's unless great mathematicians in the past and present missed such a huge simplification, and this is very unlikely (in fact, this would be the first thing that'd lit a red light in my brain about myu "proof")

  8. Apr 5, 2012 #7
    ok i see now, thanks for your posts
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook