In "Meta Math!" Greg Chaitin gives a sketch of a proof of the infinitude of primes based on complexity arguments.

Here I want to give a fuller version of that proof.

The gist of his proof is that if there were only a finite number of primes then as each number can be written as a product of primes (we don't require the uniqueness of the prime factorisation for this just that at least one exists), for some sufficiently large there are insufficient primes products to provide one for each of the distinct number in need of one.

Now suppose there are but a finite number of primes . Then as every number from to has a prime factorisation we may write for any :

.

where .

Now there are possibilities for , but different prime products less than equal to . So we have:

But as , this last inequality is for sufficiently large a contradiction, so there cannot be but a finite number of primes.

RonL - There appears to be something wrong with our b****y LaTeX today Chatfield