Prime Number Lab: Post 1

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

7 thoughts on “Prime Number Lab: Post 1

  1. Samuel Coskey

    I like to think of prime numbers as the “basis for all numbers”. Any number can be written as a product of prime numbers. So, optimistically speaking, understanding all numbers should reduce to understanding the prime numbers. That is, maybe when proving a theorem you can say “first let’s prove it for primes, then use that information to get it for all numbers”.

  2. Marc Garland

    I think the importance of primes to mathematics really cannot be justified by words. Your proof that there are infinite primes is very clear and easy to follow, so good work on that. If I were to give any advice from my reading of your post, I would suggest that you delve a little deeper into definitions, particularly when referring to the Sieve method. That was a little unclear to me. Interesting post!

  3. Jordan

    The first paragraph gives some insight as to what is going to be looked at in regards to primes. My only question is besides finding that we can prove that there are infinitely many primes, what is going to be looked at? Why are they such a large basis for modern number theory?

    1. Samuel Coskey

      This is a good question. Actually, the primes aren’t only the basis for number theory, they are the primary subject of study in number theory. So why are the primes (and number theory) so important? One answer was mentioned in the post: cryptography. But there must be many other answers…

  4. Ken Coiteux

    What exactly is the sieve method? Some people may not have ever have seen or heard of this method….I’ve only seen it twice in my math studies…..and only within the past couple of years.

  5. Pingback: Prime Numbers – Expanded Modivations and Definitions | MATH 287

  6. Pingback: Prime-Generating Functions | MATH 287

Comments are closed.