This blog post is in honor of David M. Bressoud, who was my advisor and friend while at Macalester. It’s his 60th birthday today! He is currently president of the Mathematical Association of America, which is a great honor. I think I took 24 credits (of a total of I think 128) with him, like a hawk to him I was… He was arguably the best teacher I have ever had.
In my first class with Professor Bressoud, and in my first week in college I read A Mathematician’s Apology by the English Mathematician G.H. Hardy. In a testament to the potential for elegance in mathematical proof, Hardy presented 2 simple proofs that are accessible to everyone who has survived high school math – that there are infinite prime numbers and that the square root of 2 is irrational. My favorite of the two follows:
Euclid’s Proof of the Infinitude of Primes (c. 300 BC)
There are infinite prime numbers (which implies there is not a largest prime number).
(taken from Wikipedia)
Take any finite list of prime numbers p1, p2, …, pn. It will be shown that some additional prime numbers not in this list exist. Let P be the product of all the prime numbers in the list: P = p1…pn. Let q = P + 1: 1 more than this product. Then, q is either prime or not:
- If q is prime then there is at least one more prime than is listed.
- If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. Then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list.
This proves that for any finite list of prime numbers, there is a prime number not on the list. Therefore there must be infinitely many prime numbers.
Aren’t that pretty?
Thank you David Bressoud for being awesome + HAPPY 60th BIRTHDAY!