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.
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
PAUL ERDOS – N IS A NUMBER