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 2^k) Since $s^2<N$ , we have $s<\sqrt{N}$ .