## Complexity based proof of infinitude of Primes

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 $N$ there are insufficient primes products $\le N$ to provide one for each of the $N$ distinct number in need of one.

Now suppose there are but a finite number of primes $p_1, .. , p_M$. Then as every number from $1$ to $N$ has a prime factorisation we may write for any $n \in \{1..N\}$:

$n = p_1^{k_1}\,p_2^{k_2} .. p_M^{k_M}$.

where $0 \le k_i \le \log_{p_i}(N)$.
Now there are $N$ possibilities for $n$, but $\le \prod_{i=1,..M} \log(N)/ \log(p_i)$ different prime products less than equal to $N$. So we have:

$N \le \log(N) \prod_{i=1..M} 1/\log(p_i) = K \log(N)$

But as $\lim_{N \to \infty} N/\log(N) = \infty$, this last inequality is for sufficiently large $N$ 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