It is such a pretty proof that it should be taught on aesthetic grounds alone. Here it is in all its glory.

We are going to prove that given any finite list of primes, we can always find an additional prime not in the list. Given a list of primes p1, p2,...,pn, Let P = (p1*p2*...*pn)+1. P may be a prime, in which case we are done, since P is greater than all the p values, and so can’t be equal to any of them. If P is not a prime then it must be divisible by primes. P is not divisible by any of p1, p2,... ,pn since P divided by any of them leaves a remainder of 1. Therefore all the primes that divide P must be different from p1,p2,..., pn. QED