My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
December 8th, 2008, 09:58 AM   #1
Senior Member
 
Joined: Nov 2007

Posts: 258
Thanks: 0

A new proof of the infinitude of primes

I discovered this proof using the basic idea of the sieve of Eratosthenes. Enjoy!

http://monkeytex.bradcater.webfactional ... f/?uid=470
brunojo is offline  
 
December 8th, 2008, 12:41 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: A new proof of the infinitude of primes

The proof is correct, good job.
CRGreathouse is offline  
December 8th, 2008, 04:10 PM   #3
Newbie
 
Joined: Dec 2008

Posts: 1
Thanks: 0

Re: A new proof of the infinitude of primes

Hi Bruno.

"And since the second term is nonzero, sn < 1 for all n, and hence there are in nitely many primes."

If you run your argument for all n, you are sieving with an infinite number of primes p_n, which is what you're trying to prove.
Sakura-chan is offline  
December 8th, 2008, 04:32 PM   #4
Senior Member
 
Joined: Nov 2007

Posts: 258
Thanks: 0

Re: A new proof of the infinitude of primes

Hello Sakura!

Well the idea is that for any finite n, s_n < 1. Hence there is at least one number which has not been crossed out; i.e. one number which is not divisible by the primes p_1, ..., p_n.

Obviously s_n converges to 1, but it is never 1.

I'm not exactly sure what you are trying to point out!
brunojo is offline  
December 10th, 2008, 07:13 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: A new proof of the infinitude of primes

Quote:
Originally Posted by Sakura-chan
"And since the second term is nonzero, sn < 1 for all n, and hence there are in nitely many primes."

If you run your argument for all n, you are sieving with an infinite number of primes p_n, which is what you're trying to prove.
The proof uses only finitely many primes at a time. At each step, the choice to use one more prime is justified, since there remain numbers not divisible by any prime so far. So only half the integers are divisible by 2; thus there is at least one more prime. This justifies the step using some other prime (we know it's 3, but the proof doesn't require that -- only that the prime is greater than 1), which in turn justifies using a third prime, etc.

In essence:
* Start with 2. It is a prime which divides half the integers.
* 2 doesn't divide the odd numbers, so amongst the odd numbers there is at least one prime. Choose it to be p.
* The set {2, p} divides only (1 - 1/2)(1 - 1/p) of the primes, so amongst the numbers relatively prime to 2 and p there is at least one prime. Choose it to be q.
* The set (2, p, q}...

This uses the Axiom of Choice.
CRGreathouse is offline  
December 11th, 2008, 07:14 PM   #6
duz
Senior Member
 
Joined: Oct 2008

Posts: 215
Thanks: 0

Re: A new proof of the infinitude of primes

We could use the idea to prove the infinitude of primes. But I think we'd better using the following approach.
Assumming there're only finite primes, and all of them are
Let
Let T to be the union of natural number divisible by one of .
It is easy to calculate the number of integers in intersection of and T.
duz is offline  
December 12th, 2008, 07:57 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: A new proof of the infinitude of primes

That variation actually proves an upper bound on p_n -- though not a very good one.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
infinitude, primes, proof



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proof Regarding Primes to a Power magnuspaajarvi Applied Math 1 February 8th, 2014 10:08 PM
The proof of the Twin Primes conjecture Al7-8Ex5-3:Fe#!D%03 Number Theory 3 September 30th, 2013 04:52 PM
Proof of infinite of Sophie Germain primes ibougueye Number Theory 1 February 21st, 2012 06:05 PM
Help with an infinite primes of the form proof WheepWhoop Number Theory 7 October 20th, 2011 05:09 PM
Reciprocal sum of primes diverges... proof? alpah Number Theory 5 December 30th, 2006 01:05 PM





Copyright © 2019 My Math Forum. All rights reserved.