|Proof of the Infinity of the Prime Numbers|
The standard proof is due to Euclid:
Suppose p is a prime number, and consider the number defined as 1 plus the product of all prime numbers less than or equal to p, that is:
n = 2*3*5*7*11*13*....*p + 1
If n itself is prime then there is a prime greater than p.
Suppose n is not prime, then there is a number m such that m > 1, m < n and m divides n exactly. Let q be the smallest such number.
Suppose q is not prime, then there would be a divisor r > 1 of q such that r < n and r divides n exactly, so q would not be the smallest such number. Thus q is prime.
Suppose q <= p, then q is one of the primes in the definition of n above, so n/q would equal an integer plus 1/q, which is impossible, since q divides n exactly. Thus if n is not prime then there is a prime greater than p.
Thus whether or not n is prime there is a prime greater than p.
Thus for any prime number there is a larger prime number, so there are infinitely many prime numbers.
There is a simpler proof, given in 1878 by the eminent mathematician Kummer:
Suppose the number of primes is finite: p1, p2, ..., pk, and let n be the product of all these primes. n - 1 > pk so is not prime, so there is some i such that pi divides n - 1. Since pi also divides n, pi divides n - (n - 1) = 1, which is absurd. Thus the number of primes is infinite.
|Prime Factors||Hermetic Systems Home Page|