Prime Numbers

The primes keep going up

There is an infinite number of primes. Here's one proof.

Multiplying the primes and adding 1

In this proof by contradiction one assumes there's a limited number of primes, but it turns out you can create a new prime number larger than those in your original list. We have a contradiction, so our original assumption was false.

The proof, traceable to Euclid,1 appears in many sources including [1].

Proof

There are infinitely many primes.

Why?

Because assuming there is a finite number of them produces a contradiction.

Why?

Because if you know all the primes you can multiply them together and add 1, producing a number that is either a new prime or has a prime factor that wasn't in our list.

Why?

The product of our primes plus 1 leaves no remainder when divided by any of those primes.

Why?

The product plus 1 will leave a remainder of 1. This will produce a contradiction, so our original assumption was false.

Why?

Either this big number is prime or it's not.

In the first case it would be prime, and bigger than our previously known primes because we multiplied them all (and added 1) to get this new number. So this new prime number would be larger than the other prime numbers, and hence we didn't know all the primes to begin with: contradiction.

In the second case it would be non-prime, so it has a prime factor. But none of the prime factors we knew about divides into this new number. So we have a contradiction.

Sources
1. Humphreys, J.F., and M.Y. Prest. Numbers, groups, and codes. Cambridge: Cambridge University Press, 1989 [1995 repr.].