# Complexity based proof of infinitude of Primes

• Feb 10th 2007, 01:29 PM
CaptainBlack
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 $\displaystyle N$ there are insufficient primes products $\displaystyle \le N$ to provide one for each of the $\displaystyle N$ distinct number in need of one.

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

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

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

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

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