Why Are Primes So Fascinating? From the Ancient Greeks to Cicadas

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:

We can use factor trees to find the prime factors of a composite number. Photo courtesy of Sarthaks eConnect.

This makes prime numbers the building blocks of all numbers. No wonder mathematicians wanted to learn more about them!


Observations

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):