# Paul Erdos’ Proof that there are Infinite Primes (with Examples)

Every integer can be uniquely written as $rs^2$, where $r$ is square-free (not divisible by any square numbers). For instance, 6 is square-free but 18 is not, since 18 can be divided by $3^2$.

We can do this by letting $s^2$ to be the largest square number that divides $n$, and then let $r=n/s^2$. For instance, if $n=108$, $6^2$ is the largest square number that divides 108, so we let $r=108/6^2 = 3$.

Now, suppose to the contrary that a finite number k of prime numbers exists. We fix a positive integer $N$, and try to over-estimate the number of integers between 1 and $N$. Using our previous argument, each of these numbers can be written as $rs^2$, where $r$ is square-free and $r$ and $s^2$ are both less than $N$.

By the fundamental theorem of arithmetic, there are only $2^k$ square free numbers. (The number of subsets of a set with k elements is 2k) Since $s^2, we have $s<\sqrt{N}$.

Hence, the number of integers less than N is at most $2^k \sqrt{N}$. ($2^k$ choices for $r$ and $\sqrt{N}$ choices for $s$)

i.e. $\boxed{ 2^k \sqrt{N} \geq N}$, for all N.

This inequality does not hold for $N$ sufficiently large. For instance, we can let $N=2^{4k}$, then $2^k \sqrt{2^{4k}}=2^{3k} < 2^{4k}$.

Hence, this is a contradiction, and there are infinitely many primes!

An example of how the above argument works: Suppose the only prime numbers are 2, 3, 5. (k=3)

Then, there are only $2^3=8$ square-free numbers, namely, 1, 2, 3, 5, 2×3=6, 2×5=10, 3×5=15, 2x3x5=30.

For example, if we fix $N=2^{12}$, $s< \sqrt{2^{12}}=2^6$.

$2^k \sqrt{2^{12}} = 2^3 \cdot 2^6 = 2^9 < N$, which is a contradiction.

References:

http://en.wikipedia.org/wiki/Euclid’s_theorem#Erd.C5.91s.27s_proof

An elegant proof from Erdős

PAUL ERDOS – N IS A NUMBER