Ever since the days of the ancient Greeks, mathematicians have been fascinated by prime numbers. Indivisible and fundamental, a prime number is any integer that is only divisible by two factors, 1 and itself. Listing out the first several prime numbers gives us 2,3,5,7,11,13,17,19...
This series of prime numbers is as much of a backbone in math as your own spine is in your back, yet it's extremely difficult for mathematicians to analyze, as there appears to be no sort of regularity in the sequence at all.
Unlike series such as the odd numbers 1,3,5,7,9... or the square numbers 1,4,9,16,25..., where there's a set rule to get from one to another (here: add 2 or add 2 more than you did before), there's no rule for the prime numbers. In fact, they tend to appear almost randomly across the counting numbers.
To see why this is so hard, which question do you think is easier to answer: "What is the next integer after 1,000,000?" or "What is the next prime number after 1,000,000?"
The first requires just a simple +1, to get 1,000,001, but the second requires a vast amount of trial and error and ultimately uncertainty.
This property of the prime numbers has baffled mathematicians so much that very minimal progress on understanding them has been achieved in the scheme of the last 2500 years. Today, we're no closer to understanding what happens on a small scale to get from one prime to another, but on a very large scale, mathematicians have an idea of how many primes appear in a given interval. In fact, if you're able to fully understand and solve this idea, you'll win a million dollars!
In this two-part series on primes, I'm going to walk you through some of the most important and fascinating milestones on our journey to understanding prime numbers, taking you all the way to a million-dollar question.
Prime Numbers as Building Blocks
Here's a statement that's so important we've deemed it the Fundamental Theorem of Arithmetic: Every integer has a unique prime factorization.
What does that mean? That means that every number can be divided up into prime numbers in one and only way. For example, 6 = 2*3. 2 and 3 are the only prime numbers that divide 6, and the only way we can write 6 as a product of prime numbers is 2*3.
Let's do a few more:
10 = 2*5
18 = 2*3*3
39 = 3*13
60 = 2*2*3*5
Ever wonder why an hour has 60 minutes or a circle has 360 degrees?
Ancient societies chose those numbers because a lot of prime numbers divide them. It's easy to find a quarter of an hour because 60 is divisible by 4 = 2*2, and it's easy to find a fifth of a circle because 360 is divisible by 5. This makes life easier for us to tell time and for artists and geographers to identify simple fractions of a circle in their drawings and maps.
Any number that can be written as the product of two or more prime numbers is called composite. Composite numbers are important because they have a lot of factors to work with, and each factor is easy to identify: each factor has a prime factorization that is part of the prime factorization of the overall number!
What makes prime factorizations effective to work with is that they're unique. No matter how you dissect 60, you end up with the same result:
This makes prime numbers the building blocks of all numbers. No wonder mathematicians wanted to learn more about them!
Before we continue, let's make a couple observations about primes.
Look at the sequence: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...
What do you notice?
First off, we only have one even number, 2, and the rest are odd. That's because all other even numbers are divisible by 2, so they can't possibly be divisible by only 1 and themselves. That means that after 2 and 3, all prime numbers are at least 2 apart from one another.
Some of our gaps are larger than 2, with some pairs like 7 and 11 four apart and others like 31 and 37 six apart. We seem to get larger gaps on average as we proceed, so maybe the primes are getting farther apart? To investigate this, consider these questions: How many primes are there between 1 and 10? Between 1 and 20? Between 1 and 50? Between 1 and 100? What percentage of numbers in each of these intervals are prime?
Do you think primes get rarer on average as we reach larger and larger numbers of them? If so, why?
Try to investigate and make some observations about primes yourself before you continue. This will give you an idea of how fascinating they are and why ancient cultures were so intrigued by them, and it'll give you a deeper understanding before I continue.
Euclid's Proof of the Infinitude of Primes
One of the first things that mathematicians discovered about primes was that there is an infinite number of them. The Greek mathematician Euclid made a clever argument to prove we cannot simply run out of primes. It's an argument by contradiction, and I think it's a wonderful example of inspired mathematical thinking.
Let's assume for the sake of contradiction that we only have a finite number of prime numbers. Then, we can call them 2,3,5,7... Pn, where we have n prime numbers and Pn is our largest prime number.
Then, we can form the number Q where Q is the product of all the prime numbers that exist:
Q = 2*3*5*7*...*Pn.
Let's consider Q+1. Q+1 is not divisible by 2 because Q is even and Q+1 is odd. Q+1 is also not divisible by 3 because Q is divisible by 3 and Q+1 is 1 more than Q... In fact, Q+1 is not divisible by any of 2,3,5,7...Pn, because it leaves a remainder of one when it's divided by any of them!
However, we said that every number has to be the product of one or more primes (after all, every number is either prime or composite), so Q+1 must also be the product of primes. Therefore, Q+1 must itself be a prime number, or it must be the product of multiple prime numbers that are not our list. Therefore, our list that we claimed contained every single one of the prime numbers (2,3,5,7,... Pn) does not actually contain all the prime numbers.
This is a contradiction, so there are an infinite number of prime numbers!
So, even if we're convinced that prime numbers get rarer as we move along, they never run dry.
Here's a Numberphile video on the infinitude of primes:
The Sieve of Eratosthenes
After Euclid came another Greek mathematician with a different question. We now know that there are an infinite number of prime numbers, but how can we find them? Is there a foolproof method, no matter how tedious, where we can show for a fact that a given number is prime?
Eratosthenes was an esteemed scholar who served as the chief librarian in all of Alexandria, the biggest library in all of the ancient world. You may know him because of his calculation of the circumference of Earth (yes, he knew the Earth was round way before Columbus!) but he also made an impressive dent in the world of prime numbers.
First, write down the first 100 numbers (or however many you want!). Start by circling 2, and then crossing off all its multiples (every second number after 2):
Then, circle the next number left blank (it's prime) and cross off all its multiples (this time, every third number after 3):
Do the same with the next number left blank (it's 5):
And so on. Each time, you reach a new blank number, identify it as a prime, leave it blank and cross off all of its multiples:
All image credit here goes to an amazing Eratosthenes Sieve Simulator at Visnos.com. Go check it out and generate your own sieves with even more numbers! It'll also give you a good idea of how and why this works to undercover your primes in any interval.
Here's the more standard (though less colorful) sieve:
This works because by the time you get to a number left blank, you've checked to see if it is a multiple of any of the numbers below it. If it's blank, it's managed to pass through a bunch of sieves (one for 2, one for 3, one for 5, etc), so it must be prime!
Above, we tested every single number left blank, but you can actually stop testing for prime factors at the square root of the number you're testing. Here, we only have to test the prime numbers less than sqrt(100) = 10 (or only 2,3,5,7) because none of the numbers less than or equal to 100 can be the product of two numbers greater than 10 (they'll give a product greater than 10*10=100). We only have to find one prime factor a number has to show it's composite, and therefore, all the composite numbers we have must be divisible by 2,3,5 or 7, so we only have to test those four primes!
Surprisingly, we have not made a ton of progress on testing to see if a number is prime in the last 2000 years. The main way to test a number today is exactly the same. We divide it by every prime number less than or equal to its square root, and we see if any of them divide cleanly with no remainder. If every single prime number we divide it by leaves a nonzero remainder, our number is prime!
For example, the way I would test and see if 569 is prime is to divide 569 by every prime number less than or equal to sqrt(569) = 23.8537... or 2,3,5,7,11,13,17,19,23. Each of them leaves a nonzero remainder, so none of them are factors of 569. Therefore, 569 is prime. Though, of course, this step can be skipped if it's clear a number is composite. 570 is not only even but divisible by 5, so it's composite. (It's also divisible by 3 if you know your divisibility rules! This is exactly how you'd approach the prime problem on a math competition.)
It's fascinating that despite how important and fundamental primes are, it's very difficult to discover them without a tedious, algorithmic method developed 2000 years ago. Stick around next week to see why today's mathematicians are within reach of finally making progress on understanding primes!
Cicadas: Primes as an Adaptation
Before I end today's article, let's discuss one more fun thing. Prime numbers crop up in nature too.
You know cicadas? Cicadas are insects that look something like this:
The cicadas of North America are called periodical cicadas because their life cycle is very regular. They spend most of their long lives underground feeding on fluids that the roots of deciduous trees secrete, maturing and growing until they reach the spring of their 13th or 17th year. They then swarm together in massive numbers, mate and lay eggs in the stems of the trees and other plants around them, until they all disappear, only to swarm again another 13 or 17 years later. Some periodical cicadas also have a 7-year cycle.
Why are these numbers prime? It turns out that cicadas evolved to form these prime-numbered life cycles because it's a survival strategy that helps them avoid competition and predators. Suppose the cicadas' life cycle was not every 13 years but every 12 years. Then, the cicadas' predators (like the Cicada Killer Wasp or different species of birds) that come out every 2 years, 3 years, 4 years, or 6 years will kill them every time the swarm comes out. If the cicadas instead adapt to a prime number life cycle like 13, they'll land on the same year as their predators a lot less frequently, and in some years, like the 65-year-mark on their fifth cycle, they'll miss all the predators entirely.
Another theory is that the cicadas evolved this way to avoid competition. The species of cicadas with a 13-year life cycle and the species with a 17-year life cycle would only come out at the same time once every 221 years, giving each the space to thrive and mate on their own without the food supply being eaten up by the other.
This is such a fundamental process that mathematicians who created computer programs to mimic the cicadas' life cycles and the adaptations that come about from their predators can actually generate prime numbers, just like Eratosthenes' Sieve can.
I hope you learned something interesting about prime numbers! Today, we looked at the definition of prime numbers, why they're so fundamental, two ancient Greek ideas about them, and why even Mother Nature is able to detect and use them to her advantage.
Next week, we'll discuss even more about prime numbers. We'll look at primes on a larger scale to see if we can make some discoveries, we'll talk about the million-dollar problem I keep alluding to, and we'll even discuss some of the largest primes mathematicians (and amateurs!) have discovered. We might even talk more about the history of primes through some great stories.
Note: I'd also love to do an article discussing how you can use prime factorizations and primes in general to quickly discover facts about numbers, such as the sum of their factors, the number of their factors and whether or not they're a perfect number. There's a lot of fascinating topics that come in line with all of that, and this would also be super relevant for math competitions (consider it as an introduction to competition number theory!) Let me know if that's something you'd like to see, and I'd love to write it.
This is a great article and my main inspiration in writing this one: https://kids.frontiersin.org/article/10.3389/frym.2018.00040
Here's two others that go a lot more in-depth than I did here:
Medium and Smithsonian are both amazing magazines for any math and science topic, so I'd recommend checking them out!
Experiment with the Sieve of Eratosthenes:
Here's a Numberphile video on cicadas and primes!
There's a ton of Numberphile videos on primes in general, and so many of them are fascinating, but here's a couple I'd recommend:
It turns out that if you spiral all the counting numbers, the primes land in a really interesting spot. These are often called Ulam spirals!
Cover image courtesy of Brent Yorgey, a visualization of the Sieve of Eratosthenes.
It's part of a YouTube video, which you can watch here!
That's all for today! Have a great week!