How to Prove There Are Infinite Prime Numbers?
What’s the biggest prime number? Is it the 17,425,170 digit prime discovered in January 2013? While that may be the largest prime number known today, it’s certainly not the biggest…because there isn’t a biggest! Why? Keep on reading to find out.
Jason Marshall, PhD
Listen
How to Prove There Are Infinite Prime Numbers?
Today we’re going to talk about two things that every math fan loves: prime numbers and infinity. In particular, we’re going to talk about how it is that we can be sure that there are an infinite number of prime numbers. Because there are an infinite number of them, right?
Well, it certainly seems like there should be, but how do we know without a doubt that there are indeed an infinite number of prime numbers? In other words, how can we use math to prove it? Stay tuned because that’s exactly the question we’ll be answering today!.
What Are Prime Numbers?
Before we start proving anything about prime numbers, we’d better first remind ourselves just what prime numbers are all about. The most basic place to start is with the idea that a prime number is any integer that is only divisible by itself and the number 1. Put another way, a prime number is any number that cannot be created by multiplying two smaller numbers together.
Numbers that aren’t prime are known as composite numbers. And the amazing thing is that every one of the infinite number of composite numbers can be built by multiplying prime numbers together—that’s why they’re called composite numbers! For example, the composite number 35 can be built by multiplying the primes 5 and 7, the composite number 56 can be built by multiplying the primes 2x2x2x7, and so on.
Which—and I think you’ll agree with me that this is a very cool fact—means that we can think of prime numbers as the fundamental building blocks from which all other positive integers are created!
What Is the Largest Prime Number?
But exactly how many of these prime number building blocks are there? Is there a limit to how big they can be? Well, in some sense it feels like prime numbers must go on and on getting bigger and bigger forever. After all, that’s what integers do—why shouldn’t prime numbers do it, too? And while that seems reasonable, the truth is that seeming reasonable doesn’t make it so. In math, we need to prove it.
In math, we need to prove it.
But before we prove that there is no upper-limit to the size of prime numbers, let’s take a quick look at the state-of-the-art in the prime number finding game. The history of how people have looked for larger and larger prime numbers is actually rather fascinating. As you can imagine, searching through the infinitely large stack of integers for large prime numbers is a ton of work, and for a long time before the availability of powerful non-human computers, it was painful, slow, and downright laborious work.
In 1951, before the dawn of electronic computer wizardry, the largest known prime number was 44 digits long. Yes, that’s a pretty big number, but it’s teeny-tiny compared to the 17,425,170 digit prime number that was discovered in January 2013. If progress continues along the current trend, the first 1 billion digit prime will be discovered within a few decades (perhaps even sooner).
But will this trend ever stop? Does the list of primes go on and on forever?
What Is a Mathematical Proof?
To answer this question once and for all, we need to resort to what’s called a mathematical proof.
What’s that?
The idea is actually fairly simple. A mathematical proof is nothing more than a logically sound sequence of arguments (each of which follows from the previous) that succeeds in convincing other people (in particular other mathematicians) that an idea is true.
As many people have written, mathematical arguments aren’t like the arguments made in a court of law. In math land, “beyond a reasonable doubt” is not a viable destination. The only way for a proof to actually prove anything is for it to do so without any holes whatsoever. In other words, for a proof to stand the test of time, its logic must be unequivocally correct—not just beyond a reasonable doubt, but beyond any doubt.
Euclid’s Proof of the Infinity of Primes
Which is exactly the kind of logic that Euclid used to prove that there are infinitely many prime numbers a couple of thousand years ago. And that’s exactly the proof we’re going to learn about now. To be perfectly precise (since that’s what today is all about), the exact proof that Euclid gave in his famous book Elements relies upon a slightly different flow of logic, but the underlying meaning is the same as what we’re about to reveal.
In math land, “beyond a reasonable doubt” is not a viable destination.
The idea is to first compile a list of prime numbers. Importantly, this is a finite list of prime numbers that we’re compiling here. Let’s call the numbers on our list prime1, prime2, prime3, and so on. Now, just for fun, let’s create a new number, which we’ll call Bob, that’s made by multiplying all of the prime numbers in our list together and then adding 1 to the result.
What kind of number is Bob? Well, one thing we know for sure is that Bob is bigger than any of the primes on our list (since we got Bob by multiplying all of those numbers together). Is Bob prime? Maybe. And if Bob is indeed prime, then we’ve actually found another prime number that wasn’t on our list. If Bob isn’t prime, then Bob must be composite—which means that it can be obtained by multiplying two or more primes. But we can’t get Bob by multiplying any (or all) of the primes on our original list since Bob is actually 1 larger than the product of all those primes.
Which, if you follow the logic here, means that we’ve either discovered that:
- Bob is itself a prime number not on our original list
or
- Bob has a prime factor that is not on our original list.
Either way, we’ve discovered that our original list was incomplete, and that we need to add a new prime number to it. And here’s the cool part. We can start over again and go through this same procedure with our now slightly larger list of prime numbers (which includes Bob or Bob’s prime factor). And you know what happens? We find that there must be yet another prime number that isn’t on our new list. And then again, and again, and again. Which means that this logical argument proves that our finite list can never be completed, and therefore that there is actually an infinite number of prime numbers.
Euclid was a pretty clever dude, don’t you think?
Wrap Up
OK, that’s all the math we have time for today.
Please be sure to check out my book The Math Dude’s Quick and Dirty Guide to Algebra. And remember to become a fan of the Math Dude on Facebook where you’ll find lots of great math posted throughout the week. If you’re on Twitter, please follow me there, too.
Until next time, this is Jason Marshall with The Math Dude’s Quick and Dirty Tips to Make Math Easier. Thanks for reading, math fans!
Spiraling clock and swirling numbers images courtesy of Shutterstock.
About the Author
Jason Marshall is the author of The Math Dude’s Quick and Dirty Guide to Algebra. He provides clear explanations of math terms and principles, and his simple tricks for solving basic algebra problems will have even the most math-phobic person looking forward to working out whatever math problem comes their way.