My Math Forum A new proof of the infinitude of primes
 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 $p_1,p_2,...,p_s$ Let $N_h={x|x<=h*p_1*p_2*...*p_s}$ Let T to be the union of natural number divisible by one of $p_1,p_2,...,p_s$. It is easy to calculate the number of integers in intersection of $N_h$ 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 Display Modes Linear 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