As I mentioned in my previous post, *prime numbers* are numbers which have exactly 2 divisors: themselves and 1. This means that 1 itself isn’t prime, which is very important! Prime numbers are fundamental in number theory, which is the study of positive integers and divisibility. This is because of unique factorization, which is the property that every number can be written in exactly one way (where the order of the divisors doesn’t matter) as the product of prime numbers where primes can be used more than once (this fact requires careful proof but we’ll assume for now). So prime numbers are the building blocks of all numbers.

A very important result that there are an infinite number of primes was proved over 2000 years ago by the Greek mathematician Euclid (although there’s some debate about what he actually proved). I will prove this in two different ways here.

Proof #1: This proof is a , which is where you start by assuming the opposite of what you want to prove and show that the assumption is impossible by finding an impossible consequence.

Assume to the contrary that there are actually a finite number of primes, which we can let be (the subscripts indicate that not all of the p’s are the same and that there are n of them). By unique factorization, this means that every number can be written as a product of these primes. However, consider the number , taking the product of all of the primes and then adding 1. This number is not divisible by *any* of the primes . Therefore it has no prime factorization, which is a contradiction. So, since if there were a finite number of primes that would be a problem, we have shown that there are an infinite number of primes!

Proof #2: While proof by contradiction is extremely useful and is often the only good way to prove things, in this case there is a direct way (without contradiction) to prove the infinitude of primes as well, if you don’t like the contradiction way. It’s more like what Euclid said. It is:

For any finite set of primes , the number is divisible by another prime which is different from those n primes. Therefore, we can make any set of primes bigger and bigger, so there are an infinite number of them.

And now for some nerdy humor, a quote by Noga Alon, a famous Israeli professor: “I was interviewed on the Israeli radio for five minutes and I said that more than 2000 years ago, Euclid proved that there are infinitely many primes. Immediately the host interrupted me and asked, ‘Are there still infinitely many primes?’ ” 🙂