Everything Everywhere Daily: History, Science, Geography & More - Prime Numbers (Encore)

Starting point is 00:00:00 The following is an encore presentation of Everything Everywhere Daily. 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're one of the simplest aspects of mathematics to understand. Yet, they remain at the center of some of the most puzzling problems in mathematics today. Learn more about prime numbers, what we know about them, and what we don't know, on this episode of Everything Everywhere Daily. What if your perceptions about the past were wrong? ThruLine is a podcast that takes you back in time to uncover the parts of the story that may have gone unnoticed.

Starting point is 00:00:55 It effectively turned day into night. And how it shaped the world now. Time travel with us every week on the ThruLine podcast from NPR. A prime number is a really simple concept, so simple that it's 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 one. Any number that is not prime is called a composite number, and one is considered to be neither prime nor composite. So, for example, two, three, five, seven, and eleven are all prime numbers. Two is the only even prime number, as all even numbers are divisible by two. The first text we know of that references prime numbers

Starting point is 00:01:40 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 that there are an infinite number of prime numbers. This is actually pretty easy to prove, so I'll just do it right here. Assume for a moment that there are only a finite number of primes. If you multiply all the primes together and add one, you have a number that is not evenly divisible by any other prime number. Hence, it must be a prime number. Because the original stipulation was that the number of primes was finite and we used them all, you found another

Starting point is 00:02:20 that wasn't. So the number of primes is infinite. Any prime number calculated this way is known as a Euclid prime number. The first four Euclid prime numbers 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. Let's take, for example, the number 108. 108 is even, so it can be divided by two. 108 equals 2 times 54. 54 can be broken down into 2 times 27. 27 is 3 times 9, 3 is a prime number, and of course, 9 is 3 times 3 times 3. So the prime factorization of 108 would be 2 times 2 times 3 times 3, or more simply, 2 squared times 3 cubed. Every number can be broken down this way,

Starting point is 00:03:12 which is why prime numbers are considered to be 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 a number line, and then remove all the numbers which are a multiple of a prime. So if we start with two, we remove all the numbers which are a multiple of two, aka the even numbers. And then we go to three and remove any number which is a multiple of three. And then you go to five and remove all the numbers which are divisible by five and so on. This is actually an ancient technique called the sieve of Aristotthenes, which was named after a third century BC Greek mathematician named Aristotanese 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.

Starting point is 00:03:58 If we look at the first 100 numbers, 25% are prime. The first thousand numbers, the percentage goes down to 16.8. And for the first billion numbers, it's just 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 numbers by hand, or by 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 Riemann hypothesis. Explaining the Riemann hypothesis is far beyond the scope of

Starting point is 00:04:42 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's become what most people would probably consider the greatest unsolved problem in mathematics. In fact, there is a million dollar bounty on the problem, which will be given to whoever can prove it. Proving the Riemond 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 that it is a prime number would be to calculate it. There are different

Starting point is 00:05:26 ways for how you can run a calculation to check to see if a number is prime, but they're all computationally intensive. The best system developed so far was announced in 2002 by a team from the Indian Institute of Technology, Kampur, known as the Agrawal-Caal-Saxena primality test, or A-KS primality test. It runs in what's known as Polynomal time. It still isn't easy, but it's far easier than what it was. There are some special types of prime numbers. One of the most interesting are called Mersenne Primes. Mersen primes are all of the form 2 to the N minus 1. You're probably familiar with many of the powers of two from computers and storage. 128, 256, 512, 1024, etc. For example, 2 to the power 5 is 32, minus 1 is 31, which is a prime number, which makes 31 a Mersenne prime.

Starting point is 00:06:16 There are actually very few Mersenne primes, 51 so far to be precise, and it isn't even known if the number of Mersen 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 Lamer primality test. The implication of this is that if you want 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 Mersen Prime Search, or GIMPS, where thousands of people contribute computing power to look for the next largest prime number.

Starting point is 00:06:59 If you ever see a story on the news about the discovery of the largest prime number, it's almost always going to be a Mersenne Prime. The largest known prime number was discovered in 2018 by the GIMPS Project. The number is two raised to the power of 82,589,993 minus 1. That ginormous number, if written out in its entirety, would have 24,862,48,000. 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 that number out without using any commas to format the number, it would take about 50 books, depending, of course, on the font. The entire number

Starting point is 00:07:46 written out in an ASCII file can be found online and downloaded. The plain text file is 13.64 megabytes, and I actually downloaded it when researching the show, and yeah, it's just a file with 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 Format's little theorem, not to be confused with his last theorem, which can check to see if a certain number is prime. The problem is, there are composite numbers that can also pass the test. These composite numbers are known as pseudoprimes. I actually did a project on for Mazlil theorem in my mathematics senior seminar, and I wanted to give a shout out to Professor Stan Wagon,

Starting point is 00:08:27 who taught the course and I know listens to the show. And he was also the guy who created the bicycle with square wheels that can ride smoothly. And 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 mathematics, mathematicians didn't think there was any real application. The noted 20th century mathematician David Hilbert worked on number theory precisely because he thought it was of no military value. Well, it turns out that prime numbers have an extremely important practical use.

Starting point is 00:09:04 Cryptography. In 1977, three cryptographers from MIT, Ron Rivest, Adi Shamir, and Leonard Adelman 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 really 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 trapdoor function.

Starting point is 00:09:38 It's 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. Everything Everywhere Daily is an Airwave Media Podcast. The associate producers are Thor Thompson and Peter Bennett. If you'd like to

Starting point is 00:10:22 support the show, you can do so over at patreon.com. And remember, if you leave a review or send in a question, you two can have it read on the show.

Everything Everywhere Daily: History, Science, Geography & More - Prime Numbers (Encore)

There aren't comments yet for this episode. Click on any sentence in the transcript to leave a comment.