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".