User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 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 December 8th, 2008, 12:41 PM #2 Global Moderator   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. 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. 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! December 10th, 2008, 07:13 AM   #5
Global Moderator

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. December 11th, 2008, 07:14 PM #6 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. December 12th, 2008, 07:57 AM #7 Global Moderator   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.  Tags infinitude, primes, proof Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post magnuspaajarvi Applied Math 1 February 8th, 2014 10:08 PM Al7-8Ex5-3:Fe#!D%03 Number Theory 3 September 30th, 2013 04:52 PM ibougueye Number Theory 1 February 21st, 2012 06:05 PM WheepWhoop Number Theory 7 October 20th, 2011 05:09 PM alpah Number Theory 5 December 30th, 2006 01:05 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      