Prime numbers are important to study because they are largely the basis for what we consider to be modern number theory. Understanding prime numbers and their distribution can help us solve problems in fields such as cryptology. Prime numbers have also been looked at since mathematics as we understand it came into being. So, by studying prime numbers, we are studying a vast history of research and theorems that mathematicians have discovered over the years.
We relate this motivation to process with an introduction into the process of finding primes, and move onto proving why we can find these primes by proving that the list of primes is infinite.
Our first observation begins with the Sieve method, which is the most basic method to find primes, but also the most computationally expensive as the numbers we work with get larger.
Euclid’s proof shows that the Sieve method can be used infinitely to find any number of primes we desire.
Euclid’s Proof of Infinite Primes:
Theorem: There are an infinite number of primes.
For the sake of argument, let’s let there be a finite number of primes, so n primes exist.
Let’s let M be an integer greater than 1. Like all integers greater than 1, it is either prime, or composite. Let’s let M be composite, so M is the product of primes. So, let M be the product of all the primes in our list. This means that M=p1*p2*p3*…*pn. What do we know about M+1? Well, it’s an integer greater than 1, so it’s either prime or composite. Let’s let M be prime. Then, either M+1 is a prime not on our list. Uh oh :(.
Now, let’s let M+1 be composite. This means that p|(M+1), where p is a prime from our list. But, that same p would also divide M. This is a contradiction because consecutive numbers are co-prime. This means that they cannot share a divisor greater than 1. So there must be a prime not on our list which divides M+1. So, there is at least one more prime that is not included in our list, so our list cannot be complete. Thus, the set of all primes is an infinite set, and there are an infinite number of primes.
To Next Post: Expanded Motivations and Definitions