## To Infinity and Beyond

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 $p_1, p_2, p_3, \dots, p_n$ (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 $p_1 \cdot p_2 \cdot p_3 \dots \cdot p_n + 1$, taking the product of all of the primes and then adding 1.  This number is not divisible by any of the primes $p_1, p_2, p_3 \dots, p_n$.  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 $p_1, p_2, \dots, p_n$, the number $p_1 \cdot p_2 \cdot \dots \cdot p_n + 1$ is divisible by another prime $p_{n+1}$ 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?’ ” 🙂

### 7 responses to this post.

1. Posted by Max on August 31, 2010 at 6:34 pm

Hi meena. This is an ambitious blog. You should add the proof that every number can be uniquely factorized into primes. You should put up some proofs involving Pascal’s Triangle identities. You should also prove the Poincare conjecture (no longer a conjecture) and Fermat’s Last Theorem.

2. Posted by Ben Zinberg on August 31, 2010 at 9:38 pm

You say that to make proof #2 *rigorous* you need induction, but most mathematicians would consider the proof rigorous as is. There are tons of places where induction is used implicitly. For example, in proof #1 you need induction to define the expression p_1 * … * p_n (or in some sense, to prove that it exists).

3. Posted by Jason on September 4, 2010 at 1:39 pm

Hi, Meena! Nice blog! (The quote at the end is also very amusing.)

I’m going to pick at your (lack of) rigor/abstractness. :-Þ

> prime numbers are numbers which are only divisible by themselves and 1
That’s not a sufficient definition (1 is not prime), and generalizes to what irreducible, not prime. A prime number $p$ is any number that is not a unit with the property that if p divides a*b, p divides a or p divides b. (An irreducible number is a non-unit number that whenever you write it as a product a * b, either a or b is a unit.)

> in exactly one way as the product of prime numbers
You didn’t specify what you mean by “one way”. I can write 6 as a product of primes in at least two ways: 6 = 2 * 3 = 3 * 2.