# 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 2* ^{k}*) 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.

The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth

References:

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

http://www.johndcook.com/blog/2011/10/25/erdos-proof/

PAUL ERDOS – N IS A NUMBER