Prime Numbers

Podcast Transcript

Prime numbers are considered to be the building blocks of mathematics. Every natural number can be broken down into the constituent prime numbers that make it up.

Prime numbers have been known since antiquity and they are one of the most simple aspects of mathematics to understand, yet they remain at the center of some of the most puzzling problems in mathematics.

Learn more about prime numbers, what we know about them, and what we don’t know, on this episode of Everything Everywhere Daily.

A prime number is a really simple concept. So simple that it is one of the first mathematical concepts that was known to the ancients.

A prime number is simply a number that is only divisible by itself and 1. Any number that is not prime is called a composite number.

1 is considered to be neither prime nor composite.

So 2, 3, 5, 7, and 11 are all prime numbers. 2 is the only even prime number as all even numbers are divisible by 2.

The first text we know of that references prime numbers is a mathematical text from ancient Egypt which dates back to the year 1550 BC.

The first person to explicitly talk about prime numbers as prime numbers was the ancient Greek mathematician, Euclid.

Euclid proved two important theorems that are central to prime numbers. The first was proving that there is an infinite amount of prime numbers.

This is actually pretty easy to prove, so I’ll just do it here. Assume for a moment that there are only a finite number of primes. If you multiply all the primes together and add 1, you have a number that is not evenly divisible by any other prime number, and hence, it must be prime.

Because the original stipulation was that the number of primes was finite, and you found another one that was, the number of primes is infinite.

Any prime number calculated this way is known as a Euclid Prime Number. The first four Euclid Primes are 3, 7, 31, and 211.

The second closely related theorem is known as the fundamental theorem of arithmetic, also known as the prime factorization theorem.

This states that any number can be broken down into component prime numbers.

Take for example the number 108. 108 is even, so it can be divided by 2. 108=2*54. 54 can be broken down into 2*27. 27 is 3*9. 3 is a prime number, and 9 of course is 3*3.

So 108 is 2*2*3*3*3 or 2² * 3³.

Every number can be broken down this way, which is why prime numbers are considered the building blocks of numbers.

Even though there are an infinite number of primes, the density of prime numbers has to decrease over time.

Think of all the numbers on the number line, and remove all the numbers which are a multiple of a prime. So if we start with 2, we remove all numbers which are a multiple of 2, aka all of the even numbers.

Then we go to 3 and remove any number which is a multiple of 3. Then you go to 5 and remove all the numbers divisible by 5, and so on.

This is actually an ancient technique called the sieve of Eratosthenes which was named after a 3rd century BC Greek mathematician named Eratosthenes of Cyrene.

The density of prime numbers is always decreasing.

If we look at the first 10 numbers, we find that 40% of those are prime. If we look at the first 100 numbers, 25% are prime.

For the first 1000 numbers, the percentage is 16.8.

For the first billion numbers, it is a bit over 5%.

The number of prime numbers below any given number is the prime counting function, and the only way to accurately calculate it is to actually count the prime number by hand…or computer.

There is a theorem known as the prime number theorem which approximates the prime counting function for any given number. The actual function which approximates the prime counting function has been improved and tweaked over time, but this brings us to one of the mysteries about prime numbers.

The Reimann Hypothesis.

Explaining the Reimann Hypothesis is far beyond the scope of this podcast and quite frankly probably not best explained on a podcast at all.

However, it has to do with the distribution of prime numbers and it has become what most people would probably consider the greatest unsolved problem in mathematics. In fact, there is a $1,000,000 bounty on the problem which will be given to whoever can solve it.

Proving the Reimann Hypothesis would have enormous implications for the world of mathematics and many other conjectures which depend on it being proven true.

All of this is important because of one simple fact: There is no way to predict prime numbers and there is no easy way to tell if a number is prime.

If you are given some very large number, the only way to know if that number is prime is to calculate it.

There are different ways for how you can run a calculation to check to see if a number is prime, but they are all computationally intensive. The best system developed so far was announced in 2002 by a team from the Indian Institute of Technology Kanpur. Known as the Agrawal–Kayal–Saxena primality test or the AKS primality test, it runs in what is known as polynomial time.

It still isn’t easy, but it is far easier than it was.

There are some special types of prime numbers. One of the most interesting are Mersenne Primes.

Mersenne Primes are all of the form 2ⁿ-1. You are probably familiar with many of the powers of 2 from computers and storage. 128, 256, 512, 1024, etc.

For example, 2⁵ is 32, minus 1 is 31, which is a prime number, which makes 31 a Mersenne Prime.

There are actually very few Mersenne Primes, 51 so far to be precise, and it isn’t even known if the number of Mersenne Primes is finite or infinite. However, what makes them special is that this particular category of prime number can be checked relatively quickly via a method called the Lucas–Lehmer Primality Test.

The implication of this is that if you wanted to find the largest known prime number, the easiest way to do it is to check for Mersenne Primes.

Mersenne Primes were often used as a test for brand new supercomputers to show off their power. There is a distributed computing project known as the Great Internet Mersenne Prime Search or GIMPS where thousands of people contribute computing power to look for the next largest prime number.

If you ever see a story on the news about the discovery of the largest prime number, it is almost always a Mersenne Prime.

The largest known prime number was discovered in 2018 by the GIMPS project. The number is 2^82,589,933 ? 1. That ginormous number if written out in its entirety would have 24,862,048 digits.

Just to put that into perspective, the average book will have about half a million characters if you include spaces. So if you printed out the number, without using any commas to format the number, it would take about 50 books….depending of course on the font.

The entire number, written out in an ASCII file, can be found online and downloaded. The plain text file is 13.64 megabytes. I actually downloaded it when researching this show, and, yeah, it’s just a whole bunch of numbers.

I should also note that there are ways to test if a number is prime using probability. Pierre Fermat discovered something known as ??Fermat’s Little Theorem, not to be confused with his last theorem, which can check to see if certain numbers are prime.

The problem is, there are composite numbers that can pass the test. These composite numbers are known as pseudoprimes.

I actually did a project on Fermat’s Little Theorem in my mathematics senior seminar, and I want to give a shout-out to Professor Stan Wagon who taught the course and I know listens to the show.

He was also the guy who created the bicycle with square wheels that can ride smoothly. If you want to know how that works, just do a search for it.

By now, you might be wondering what is the point of all this? Sure, maybe prime numbers are interesting to a mathematician, but do they have any application beyond pure mathematics?

For the longest time, most mathematicians didn’t think there was any real application. The noted early 20th-century mathematician David Hilbert worked on number theory precisely because he thought it was of no military use.

Well, it turns out that prime numbers have an extremely important practical use: cryptography.

In 1977 three cryptographers from MIT, Ron Rivest, Adi Shamir, and Leonard Adleman announced a new algorithm called RSA. This was the birth of public-key cryptography.

The heart of the system was multiplying two large prime numbers together.

Multiplying two large numbers is actually quite easy. Any computer can do it quickly.

Doing the opposite, finding the prime factors for a large number, is really really hard. Much harder than determining if a number is prime.

This is called a trap door function. It is easy to calculate, but very hard to do in reverse.

Prime numbers are also central to many cryptocurrencies for the creation of public and private keys.

So, prime numbers have a dual nature.

They are random and unpredictable, yet they also follow rules and have a type of predictability.

They were known to the ancients who discovered the basics of how they work, yet they still have mysteries that befuddle the best mathematicians today.

…and even though prime numbers were once thought to have no practical application, they are now critical to the functioning of the modern internet.