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.