Register to reply

Proving (a weaker form of) Bertrand's postulate

by stevenytc
Tags: bertrand, form, postulate, proving, weaker
Share this thread:
stevenytc
#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
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds
micromass
#2
Jan4-12, 06:46 AM
Mentor
micromass's Avatar
P: 18,038
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
#3
Jan4-12, 06:53 AM
P: 12
ok, I understand now, thanks!

TheFurryGoat
#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
#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
#6
Jan6-12, 10:18 AM
Mentor
micromass's Avatar
P: 18,038
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
#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
#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 Astronomy & Astrophysics 0