"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Sunday, May 16, 2010

Infinitude of primes, courtesy of Euclid

I love this proof:
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 = p1p2...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. (Wikipedia)

* If some integer k divides two integers a, b then k divides a-b.
This will be immediate to some, but I'll provide a small proof of that fact for clarity's sake.
k divides a -->  a = kx, where x is an integer, by def. of "divides"
k divides b -->  b = ky, where y is an integer, by def. of "divides"
a-b = kx - ky = k(x-y)
but x-y is an integer
Hence k divides a-b, by definition of "divides".

No comments: