In a recent diary I introduced this series on math. This is the first of the regular diaries. We will explore some basic properties of prime numbers, including Euclid's proof that there is an infinite number of them. It's a beautiful proof, and doesn't require any advanced math to understand. In fact, you just need the four basic arithmetic operations: Addition, subtraction, multiplication, and division (you really don't even need subtraction).
I'll also talk a little about arithmetic, number theory, and esthetics.
This diary series is intended to be understandable by people without a heavy math background. Others who wish to post a diary in the series are welcom, but please ask me. If you have an idea for a topic, please let me know. And if you want to help explain stuff in comments, feel free, but be nice. There are no dumb questions.
So join me below the fold
The most basic mathematical objects are what's known as the counting numbers (aka the natural numbers, or, for those who like fancy words, the positive integers - some people use `natural numbers' to include 0, but we're talking about just the positive ones). These are the numbers you count with (we'll discuss other numbers in later diaries): 1, 2, 3, ....
The ellipsis (...) is math notation for `and so on'. Kids learn early that there is no biggest number - there are an infinite number of numbers. In a later diary, we'll talk about some interesting things about infinity, but, for now, let's just say that it means that, no matter how big a number you name, I can name a bigger one. Some kids go through a period where they are fascinated by large numbers - when kids learn I like math, some start asking questions like "What's 1 billion minus 1 million?" or "What's the biggest number with a name?"
Mathematicians spend a lot of time thinking about these positive integers. When they do this, they are usually engaged in number theory, which is sometimes called the `higher arithmetic'. Some of this is very abstract and difficult, and we won't go there. But number theory is the branch of math where it is easiest for novices (even kids) to ask questions that have everyone stumped. It's also a branch of math where there are a lot of questions that have interesting but understandable answers.
The counting numbers can be divided into different groups in lots of ways: Some are odd, some are even. Some are square (that is, numbers that are a number times itself 1, 4, 9, 16 and so on) and some are not. One of the most important ways to categorize numbers is as primes or composites. A prime number is one that can't be evenly divided by any number but itself. A composite number is one that isn't prime. So
2 is prime
3 is prime
4 is composite (2 x 2)
5 is prime
6 is composite (3 x 2)
And so on
Primes are important for lots of reasons, but one of the biggest is that every positive integer can be factored into primes in one and only one way. So:
2 = 2*1
3 = 3*1
4 = 2*2
...
28 = 7*2*2
And so on.
The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
They seem to be getting less common. Of the first 10 positive integers, 5 are prime. Of the next 10, 4 are prime. Of the next 10 (in the 30s) only 2 are prime. Of the first 100, 25% are prime; of the first 1,000, 16.8%; of the first 1,000,000, 7.8%. Do they ever stop?
No. They don't. This has been known for a very long time, since Euclid in Greece. He devised a proof. It's a kind of proof that's very common in math, called reductio ad absurdum (reduce to absurdity). In it, we first suppose that what we wish to prove is false. Then we derive a contradiction (these proofs are also known as proofs by contradiction).
So:
Theorem: There is no largest prime number
Proof: Suppose there is a largest prime number. Call it X. Now write down all the prime numbers smaller than X. (In math, the primes are often labeled as p with a subscript).
P1, p2, p3 and so on, until you get to X, the supposed largest prime
Multiply all these numbers together. Add one. So, suppose we thought the largest prime was 7 (it's ridiculous, but I am just illustrating a point), then write down the primes smaller than that or equal to that
1, 2, 3, 5, 7
Multiply them
1*2*3*5*7 = 220.
Add 1 = 221.
Let's call this number M. Clearly, M is bigger than X.
Now there are two possibilities: Either A) M (221) is prime or B) M is composite. (We know there are no other possibilities because every number is either prime or composite)
If A is true, then we have found a bigger prime than X.
If B is true, then M can't be divisible by any of the primes we used, because we added one. So, if we divide by 2, the remainder is 1. If we divide by 3, the remainder is 1. If we divide by 5, the remainder is (you guessed it) 1. So, if it's composite, its prime factors must be bigger than X.
Since both these conclusions violate the assumption that X is the biggest prime, the assumption must be wrong. There is no biggest prime.
When mathematicians finish a proof, they sometimes write QED, for quod erat demonstrum (Latin for `which was to be shown'). Euclid couldn't have written this, but one can imagine that he had a pretty elated feeling when he figured this out. It's beautiful. What does that mean? Louis Armstrong supposedly said about jazz "if you have to ask, you'll never know" and that may be true here, too. Why is this proof beautiful? Well, it uses very simple concepts to prove something deep. It has a certain surprise factor - you don't see the answer coming. But it also has a certain inevitability once it's done. I once heard Leonard Bernstein trying to describe why a piece of music was beautiful and he used similar terms.
We know a lot about primes besides that. But there are some simple things we don't know. Here's one: When there are two primes where one is 2 more than the other, they are called twin primes. The first twin primes are 1 and 3; 3 and 5; 5 and 7; 11 and 13; 17 and 19; 29 and 31. They keep going for a very long time. Everyone thinks there are infinitely many. But there's no proof.
Digression: Logarithms
When you raise a number to a power, you multiply it by itself that many times:
2^3 = 2*2*2 = 8.
5^4 = 5*5*5*5 = 625.
But mathematicians love to extend the meanings of things, so they invented fractional powers. The simplest fractional powers are roots. A square root is a number that, when squared, makes the original number
9 ^ 1/2= 3 because 32 = 9.
16 ^ 1/2 = 4 because 42 = 16
But then there are cube roots:
27 ^ 1/3 = 3 because 33 = 27
64 ^ 1/3 = 4 because 43 = 64.
Don't stop there! If you square a cube root, you get the 2/3 power. If you cube a square root, you get the 3/2 power. What fun!
64 ^ 2/3 = 16 because 641/3, squared = 4*4 = 16.
A logarithm is the opposite of a power (or exponent). A logarithm has a base - by far the most common are 10 and e (more on e in a bit). In base 10, we usually write it as log(x).
Log(100) = 2, because 102 =100
Log (1000) = 3, because 103 = 1000.
And, since you can have fractional powers you can have the log of any number greater than 0.
But the most common base for logs isn't 10, it's e, which is approximately 2.718. You can't figure out what e is exactly (I won't explain why, here) but you can get as close as you want, because
When we take logs to base e, they are called natural logs, and written ln(x).
End digression
Here's another interesting thing about primes: You can't predict, by any known method, what the next one is. But you can predict about how many there will be below a certain number. There are a few ways, but the most famous and surprising is one discovered by Gauss (perhaps the greatest mathematician ever).
Π(x) ≈x/ln(x)
Π(x) is shorthand for the number of primes less than x. The wavy equals sign means "approximately equal to". When I first saw this, I was amazed! What the ** is going on here? Why are prime numbers, which are integers, related to a fraction that involves logs to the base e, which is an irrational number? I won't get into that here. But it's true. And the approximation gets better as x gets bigger.