Proof That the Set of Prime Numbers is Infinite

Theorem: There are infinitely many prime numbers.

Proof: Suppose, contrary to the theorem, that there is only a finite number of primes. Thus, there will be a largest which we can call p. Now define a number n as 1 plus the product of all the primes:

n = (2 X 3 X 5 X 7 X 11 X...X p) 1

Is n itself prime or composite? If it is prime then our original supposition is false, since n is larger than the supposed largest prime p. So now let’s consider it composite. This means that it must be divisible (without remainder) by prime numbers. However, none of the primes up to p will divide n (since we would always have remainder 1), so any number which does divide n must be greater than p. This means that there is a prime number greater than p after all. Thus, whether n is prime or composite, our supposition that there is a largest prime number is false. Therefore, the set of prime numbers is infinite.

There is always one larger.