## Archive for August, 2010

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

### What is math anyway?

Since I’m trying to write a blog about math, I should probably explain what math is first!

Math, roughly speaking, is a vast collection of knowledge that is rigorously established. What does that mean? Proofs. Proofs are at the heart of math.

Mathematicians go crazy with proofs. In fact, they insist on making everything rigorous and basing things off of very basic assumptions called axioms. Even the simple, seemingly obvious fact that $0 \cdot n = 0$ for any number n has proof using simpler axioms about our number system.

So why do we bother proofs? Often the first step towards proving something is noticing that a certain fact is true in a lot of cases. This is a pattern. But, patterns are not enough to show a general result. For example, in the early 1800’s, the mathematicians Legendre and Gauss noticed that the expression $n^2-n+41$ is a prime number for n from 1 to 40. (A prime number is a number that is only divisible by 1 and itself, so 3 is a prime number because it cannot be broken up into more factors but 6 isn’t a prime number because it is $2 \cdot 3$.) It seems like with so much evidence, it should be true for all positive counting numbers, and that’s what they thought too. However, in the very next case, $n=41$, it fails to be prime. This is easy to see because $41^2-41+41=41^2$, which is not prime. Silly Legendre and Gauss!  Furthermore, often a proof gives us important insights that can then be applied to other problems.  The why is crucial.

Making guesses is how math evolves.  Something that is not proven but is believed to be true is called a conjecture. There are many, many important problems with the status of conjecture right at this moment. That is what current mathematicians keep themselves busy with. For example, one conjecture that hasn’t been resolved is whether or not there are an infinite number of positive counting numbers for that same expression $n^2-n+41$ where the result is prime (so even though it isn’t true for all positive counting numbers, it could still be true for an infinite number of them).  This is an open question for almost all quadratic equations (an expression with a squared term as its highest power), in fact.

In most middle and high school math classes, proofs are often left out or only partially stated. I think this is a mistake, since proofs are so key to math. Everything has a proof. So, the next time your teacher tells you something is true, try to find a proof!