Difference between revisions of "Euclid's proof of the infinitude of primes"
m |
|
(No difference)
|
Revision as of 19:18, 11 January 2008
We proceed by contradiction. Suppose there are only finitely many prime numbers; let's call them . Let
. When
is divided by any of our primes
it leaves a remainder of 1, so none of these primes divide
. Since every positive integer has at least one prime factor,
has some prime factor (possibly itself) not in the set
. Thus
does not contain all prime numbers. Contradiction! Our original assumption must have been false, so there are in fact infinitely many primes.