Proof of the Infinity of the Prime Numbers |

The standard proof is due to Euclid:

Suppose

pis a prime number, and consider the number defined as 1 plus the product of all prime numbers less than or equal top, that is:

n = 2*3*5*7*11*13*....*p + 1 If

nitself is prime then there is a prime greater thanp.Suppose

nis not prime, then there is a numbermsuch thatm> 1,m<nandmdividesnexactly. Letqbe the smallest such number.Suppose

qis not prime, then there would be a divisorr> 1 ofqsuch thatr<nandrdividesnexactly, soqwould not be the smallest such number. Thusqis prime.Suppose

q<=p, thenqis one of the primes in the definition ofnabove, son/qwould equal an integer plus 1/q, which is impossible, sinceqdividesnexactly. Thus ifnis not prime then there is a prime greater thanp.Thus whether or not

nis prime there is a prime greater thanp.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:

pand let_{1}, p_{2}, ..., p_{k},nbe the product of all these primes.n- 1 >pso is not prime, so there is some_{k}isuch thatpdivides_{i}n- 1. Sincepalso divides_{i}n,pdivides_{i}n- (n- 1) = 1, which is absurd. Thus the number of primes is infinite.

Prime Number Spiral | Hermetic Systems Home Page |