Paul Erdos’ Proof that there are Infinite Primes (with Examples)
Every integer can be uniquely written as , where 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 .
We can do this by letting to be the largest square number that divides , and then let . For instance, if , is the largest square number that divides 108, so we let .
Now, suppose to the contrary that a finite number k of prime numbers exists. We fix a positive integer , and try to over-estimate the number of integers between 1 and . Using our previous argument, each of these numbers can be written as , where is square-free and and are both less than .
By the fundamental theorem of arithmetic, there are only square free numbers. (The number of subsets of a set with k elements is 2k) Since , we have .
Hence, the number of integers less than N is at most . ( choices for and choices for )
i.e. , for all N.
This inequality does not hold for sufficiently large. For instance, we can let , then .
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 square-free numbers, namely, 1, 2, 3, 5, 2×3=6, 2×5=10, 3×5=15, 2x3x5=30.
For example, if we fix , .
, which is a contradiction.
PAUL ERDOS – N IS A NUMBER