Monday, March 3, 2008

Mathematics for Arithmeticians: Prime Numbers

I've decided to stop calling myself a computer science student — I got tired of being the computer guy — and go for mathematics instead.

People used to ask me to fix their computers. Now they ask me to calculate the tip and divide the bill when we go to restaurants, too.

Yeah, so people don't know what mathematics is any better than they know what computer science is.

Maths is not arithmetic (though arithmetic sometimes helps us do maths). Maths is not a set of facts you don't understand handed down from on high for you to remember. It's a world to explore and understand. To enjoy it, you'll want to explore yourself, but I'm going to show you some of the sights. Hopefully, a bit of high-school vocabulary and a bit of thought should be enough to understand this. *

As one of my lecturers pointed out the other day, one of the reasons the natural numbers (whole, positive numbers) are interesting is because they have two kinds of structure: additive and multiplicative. The building block of the additive structure is one: we can make any number by taking one, adding one, adding one again, etc.

But the multiplicative structure is a little more intricate. The building blocks are called "prime": the numbers you can't make by multiplying other numbers together. I'm sure you know them. 2, 3, 5, 7, 11, and so on.

And so on? Does that mean I'm too lazy to list them all. Nope... there are infinitely many primes. How do I know? I have a proof.

First off, what does it mean for there to be infinitely many primes? Clearly, it means for any prime, there is another one bigger than it. So how can we show that there is a prime bigger than p?

Take all the primes up to p, multiply them together, and add one: 2×3×5×...p + 1. This number isn't divisible by 2 (since the number is two times something plus 1, when you divide it by two you get a remainder of 1). Similarly, it isn't divisible by 3, 5, or any other prime up to p.

So either 2×3×5×...p + 1 is prime, or there is some prime number bigger than p which divides it.

So p is not the largest prime. But this argument works for any p, so there is no largest prime.

This proof is due to Euclid. We proceeded from an obvious starting point, by obvious steps (if any of them were not obvious, leave a comment and I'll explain in further detail), to a non-obvious, interesting conclusion.

I hope you think this is as beautiful as I do.

* The things I plan to present in this series are basically the subset of things that I've been thinking about and discussing with my friends which I can explain to my girlfriend, who is interested in maths but has never studied it beyond school.


  1. Scientists Ask Congress To Fund $50 Billion Science Thing

    "Another diagram presented to lawmakers contained several important squiggly lines, numbers, and letters. Despite not being numbers, the letters were reportedly meant to represent mathematics too. The scientists seemed to believe that correct math was what would help make the science thing go."

  2. This comment has been removed by the author.

  3. I do think it's as beautiful as you do. I'd be interested to hear any other proofs regarding the infinitude of primes; that's the only one I know of. And it wouldn't work if 1 were prime. That's sort of interesting philosophically, I think, if not mathematically.

  4. Oh, and btw, you're lucky to have a girlfriend whose interested in math. Mine is nice enough to pretend to listen, but that's about it.

  5. enginerd, Aigner and Ziegler's Proofs from The Book gives six, including this one.

    The others they give are not nearly as elegant, in my opinion. They are: Fermat numbers are all relatively prime, so there are infinitely many primes; any prime factor of 2^p-1 is greater than p; the number of primes below n is greater than log n; Furstenburg's topological proof; and, the sum of 1/p diverges.

  6. Yes, I know I'm late to the party, still... there anything using the Matula number, the bijection between the naturals and rooted trees? Because the primes are trivial to identify in T-space, and trivial to identify as being countably infinite.