Monday, March 10, 2008

Mathematics for Arithmeticians: Pons asinorum

In today's post, I will show Pappus's proof of the so-called Pons asinorum or Bridge of Asses. The theorem is given this name because it is the first difficult theorem in Euclid's Elements. The theorem states that the base angles of an isosceles triangle are equal.

Consider triangle ABC, with AB = BC. Now we want to prove that angle A is equal to angle C. One useful trick in geometry for proving things equal is to use congruence of triangles, but we only have one triangle.

Or do we? Pappus' trick is to look at one triangle two ways: ABC and its reflection CBA. AB = CB (by our starting assumption), BA = BC (by the same assumption), and AC = CA (they're the same line). So ABC ≡ CBA (all three corresponding sides are equal, so they're congruent). Since they're congruent, the corresponding angles are equal: angle A equals angle B.

That's it. This trick allows us to prove the theorem in just a few steps.

Why do I think this elegant? By looking at one thing in two ways, we learnt something new, and remarkably quickly. And the great thing is that you can use this trick again, to prove the converse using angle-side-angle congruence. And a trick you can use more than once is a technique.

If you followed this, well done. You have crossed the Bridge of Asses.

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.