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?’ ” 🙂

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.

Posted by meenamathgirl on August 31, 2010 at 8:06 pm

thanks max, i’ll get on those last two 😛

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).

Posted by meenamathgirl on September 1, 2010 at 8:18 am

Oh ok, I guess my standards of rigor after mathcamp are too high 😛

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.

Posted by meenamathgirl on September 4, 2010 at 2:22 pm

Thanks! By the way to do latex you have to do “dollar latex …… dollar” And I will fix the definition at least to correct for 1 not being prime, silly me!!

Posted by 2010 in review « The Power of Proofs on January 2, 2011 at 10:04 am

[…] To Infinity and Beyond August 2010 6 comments 3 […]