Proving (a weaker form of) Bertrand's postulate


by stevenytc
Tags: bertrand, form, postulate, proving, weaker
stevenytc
stevenytc is offline
#1
Jan4-12, 06:03 AM
P: 12
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.
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
micromass
micromass is online now
#2
Jan4-12, 06:46 AM
Mentor
micromass's Avatar
P: 16,700
Quote Quote by stevenytc View Post
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.
I think it's not hard to show that M will always exist. For n somewhat large.

for M exists:
5a) consider K = n + M, K ≤ 2n (from 4)
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!!

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)
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.
stevenytc
stevenytc is offline
#3
Jan4-12, 06:53 AM
P: 12
ok, I understand now, thanks!

TheFurryGoat
TheFurryGoat is offline
#4
Jan6-12, 08:34 AM
P: 42

Proving (a weaker form of) Bertrand's postulate


Quote Quote by micromass View Post
I think it's not hard to show that M will always exist. For n somewhat large.
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.
TheFurryGoat
TheFurryGoat is offline
#5
Jan6-12, 08:49 AM
P: 42
Quote Quote by stevenytc View Post
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]
.
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.
micromass
micromass is online now
#6
Jan6-12, 10:18 AM
Mentor
micromass's Avatar
P: 16,700
Quote Quote by TheFurryGoat View Post
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.
Not true. Take k=10. Then n=2*3*5*7=210. There are a lot of primes smaller than 210.
TheFurryGoat
TheFurryGoat is offline
#7
Jan6-12, 10:56 AM
P: 42
Quote Quote by micromass View Post
Not true. Take k=10. Then n=2*3*5*7=210. There are a lot of primes smaller than 210.
woops, sorry, got mixed up with my thoughts, you're right.
coolul007
coolul007 is offline
#8
Feb4-12, 10:17 PM
coolul007's Avatar
P: 234
Erdos has a very elegant proof of this theorem.


Register to reply

Related Discussions
Finding the converse of Euclid's fifth postulate (parallel postulate) Calculus & Beyond Homework 2
Proving solutions of an ODE of the form y''+by'+cy=0 Engineering, Comp Sci, & Technology Homework 2
I have a set of numbers, how do I go about proving they form a field Calculus & Beyond Homework 2
Why doesnt Bertrand's postulate imply Legendre's conjecture? Linear & Abstract Algebra 20
Bertrand's Theorem Astrophysics 0