Tag: infinite primes

Paul Erdos’ Proof that there are Infinite Primes

 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<N, 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.


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

An elegant proof from Erdős

PAUL ERDOS – N IS A NUMBER