213
edits
Changes
Jump to navigation
Jump to search
Line 9:
Line 9: + + + +
no edit summary
It is easy to prove that there are an infinite number of primes using Euclid's second theorem: Imagine there is a finite set consisting of all the primes. Multiply them all together, add 1, and call this N. N would not be divisible by any number in the set--there would always be a remainder of 1. Because all non-prime numbers can be decomposed into a product of underlying primes, N must be divisible by some prime not in the set (possibly itself), thus contradicting the assumption that the set contained all of the primes.
It is easy to prove that there are an infinite number of primes using Euclid's second theorem: Imagine there is a finite set consisting of all the primes. Multiply them all together, add 1, and call this N. N would not be divisible by any number in the set--there would always be a remainder of 1. Because all non-prime numbers can be decomposed into a product of underlying primes, N must be divisible by some prime not in the set (possibly itself), thus contradicting the assumption that the set contained all of the primes.
Another proof that there are infinitely many primes shows something stronger, namely the sum of the reciprocals of primes less than n "grows like" log(log(n)):
<math>\sum_{p\le x}p^{-1}\approx\log\log x</math>
To construct a table of all prime numbers less than ''n'', you would use a method called the [[Sieve of Eratosthenes]]. Simply write down an ordered list of all counting numbers greater than 1. Beginning with 2*2 = 4, cross out every second number:
To construct a table of all prime numbers less than ''n'', you would use a method called the [[Sieve of Eratosthenes]]. Simply write down an ordered list of all counting numbers greater than 1. Beginning with 2*2 = 4, cross out every second number: