In the rest of this course, we'll focus on mathematics that relates to calculation, number, and equation solving. These are stories that connect ancient and modern algebra, algorithms, and number theory.
To begin digging into the number theory more, we'll need to discuss prime numbers. Again, attribution isn't really possible, but this time we know one real, ancient mathematician who did a lot of amazing mathematics.
Meet Eratosthenes.
Eratosthenes was a Greek mathematician (and astronomer, librarian, historian, poet, …) who lived around B.C. Sadly, almost everything he wrote himself has been lost forever, much of it likely consumed in the fire that destroyed the great library of Alexandria.
Although we don't have access to much of his written work, we do know some of Eratosthenes's accomplishments thanks to others who've referenced or quoted him.
Eratosthenes studied numbers, and one fundamental property of numbers is this: every positive integer greater than is either prime or composite. A prime number is divisible only by itself and but composite numbers are divisible by at least one other number.
Prime numbers are like atoms (in the classical sense) — they are the building blocks out of which other numbers can be formed, but they themselves are indivisible. On the other hand, It's possible to think about composite numbers as if they are made out of primes: for example.
With many problems, breaking down composite numbers into their prime pieces is quite helpful.
Prime numbers like these are the fundamental particles of the number universe, and much of number theory is built around the fact that every number is uniquely described as a product of its prime parts.
There's one big problem, though. We know next to nothing about prime numbers themselves (and as best we can tell, this bothered Eratosthenes quite a bit).
One of the problems Eratosthenes set out to solve was a fundamental one: how do we even figure out which numbers are prime?
For small numbers, it's fairly quick to check: is prime? Let's see… it's not divisible by it's not divisible by it's not divisible by and so on.
As numbers get larger, though, checking like this gets tedious very quickly. Eratosthenes set out to find a more efficient approach.
How many of the numbers in this grid are multiples of
- numbers in this grid are multiples of
- numbers in this grid are multiples of
How many numbers from to are not multiples of or multiples of
The previous problems have hinted at a method that we can continue:
- Starting with remove all multiples of from the list.
- Choose the next non-removed number and remove all of its multiples from the list.
If we continue this procedure, which number is the last one that we'll end up using to remove a multiple of it (in addition to itself) from the list?
The method we've just employed is known as the sieve of Eratosthenes. Like a sieve, it strains the numbers and leaves behind only the ones we want: the primes.
Eratosthenes's insight was as simple as it was profound. Finding primes is hard, but finding composite numbers is easy by comparison. Since every number is either one or the other, if we find all the composite numbers and remove them, then all the numbers left over will be prime.
Eratosthenes's sieve is a brilliant technique, and it was used for over a thousand years as the most efficient available technique for finding primes. But finding the primes might just raise more questions than it answers…
Let's look at the first prime numbers, grouped by their leading digit:
What patterns are visible in the prime numbers here?
Although the primes don't have an obvious pattern, that hasn't stopped mathematicians through the centuries from looking for one.
Here's a simple formula that generates prime numbers: Placing some values for into the formula can produce a prime number.
For example, placing for gives us which is prime. Placing for gives us another prime.
Which value of will produce a composite number instead of a prime?
Many people have attempted to improve Eratosthenes's approach by calculating prime number values directly. One example: the formula produces distinct primes for every integer value of from to Without calculating anything, can you see why it definitely fails to make a prime when
But despite some temporary successes like these, no formula or generating pattern has ever been found for the primes. And even now, over years after Eratosthenes, we still don't have answers to some of the simplest questions:
- Are there infinitely many pairs of twin primes: two primes that are only two units apart, like and No one knows.
- Why is it that, after a prime ending in it seems almost twice as likely for the next prime to end in instead of No one knows. (This might be a bias that only shows up for small primes.)
- Can every even number greater than be written as the sum of two primes? No one knows.
Like the other mathematicians we'll discuss, Eratosthenes made significant progress in mapping the landscape of numbers. What drove Eratosthenes to explore the primes, though? Was it curiosity about how much was still unknown, about how many questions still needed to be answered?
Well, it often turns out that, in math, each new discovery and each new tool just helps us see that much farther into the wild tangle of that-which-we-still-do-not-know.