The Intuition Behind The Infinitude of Prime Numbers
1:22 AM
Muhammad Yusuf
, Posted in
In my Introduction to Prime Numbers post, we conjectured that the number of primes is decreasing as the counting numbers increase. In this post, we are going to discuss intuitively that there is no greatest prime, or that there are infinitely many prime numbers.
Before proceeding with our discussion, it is noteworthy to remember what we said earlier that a number can either be prime or composite. We also know that composite numbers are product of primes.
Fragment of the original "Elements" by Euclid (via Wikimedia).
Many people know Euclid for his work in geometry, but only a few know about his work in number theory. In Book IX of The Elements, Euclid proved that there infinitely many prime numbers. The discussion below is an intuitive explanation of his proof.
Let us have the following analogy:
- Assuming that the only primes that exist are in S = {2,3,5}. We multiply all the primes in set S and then add 1: (2x3x5 +1) = 31.
- If 31 is prime (in fact, it is) then our assumption that (1) is false because we found another prime not in S.
- We can probably be skeptical and say, hmmm… maybe {2,3,5,31} are the only primes. Again, we multiply multiply all the numbers in the set and add 1: 2 x 3 x 5 x 31 + 1 = 931. Is 931 prime? No. 931 = (19)(7)(7). Note that 19 and 7 are primes and not in S. Again, we found primes not in set S.
Let us summarize the steps that we have done above to look for primes.
- We multiplied all the primes in set S then added 1.
- If the result is prime, we found another prime not in S.
- If the result is composite, then it must be a product of primes. Since dividing it with any of the factors in S will give a remainder 1 (Why?), this implies that at least one of its factors is a prime not in S. Still, we found another prime not in S.
Now, steps 1-3 can go on forever because once we found a prime not in S, we can always include it in S and repeat step 1. For example, we can say maybe {2, 3, 5, 7, 19, 31} are the only primes and we proceed to 2 and 3.
Since it is possible to repeat the process infinitely, we have the following fact:
Given a finite list of primes, we can always find primes not on that list.
Hence, there are infinitely many primes.
0 Response to "The Intuition Behind The Infinitude of Prime Numbers"
Post a Comment