The Ancient Greeks loved to classify numbers. Numbers that could be represented as the ratio of two whole numbers were rational numbers. Numbers such as $\sqrt{2}$ which could not were irrational numbers. A perfect number, such as 6, is equal to the sum of its proper divisors. Amicable numbers, such as 220 and 284, are pairs of numbers where each is the sum of the proper divisors of the other.
Without a doubt, the most important of these classifications was the concept of a prime number. A prime number is any positive integer that has exactly two divisors. $5$ is a prime number but $8$ is not. $1$ is not, $0$ is not, and negative numbers are not. While the definition is clear, one might immediately ask, why should one care.
There are two big reasons why we should care. If mathematics is the study of patterns, some of the most amazing and surprising patterns relate to prime numbers. Investigating prime numbers turns out to be a royal path to deep mathematical insights. For example, one of the most important problems in mathematics today is the Reimann Hypothesis which concerns the relationship between prime numbers and the complex zeta function. By the way, if anyone solves it, there's a million dollar prize waiting to be claimed.
The other reason to care about primes is that their properties have become fundamental to the very running of global eCommerce. Prime numbers start out very common and become surprisingly rare as one starts to consider very large numbers. It turns out that determining whether a number is prime can take a significant computation effort if the prime is large enough. In fact, one of the great pursuits of spare computation capacity is the search for new primes. Each time a new largest prime is discovered, it is worthy of a news headline. For example, here is a news headline from NPR in 2018.
Because there are an infinite number of primes (more about that later) and because it is possible to find primes up to the limits of current computational power, they have become an excellent foundation for security. Indeed, this is the foundation of public key encryption. For example, RSA, one of the earliest public key encryptions is based on the difficulty of factoring the product of two large prime numbers.
But let's start smaller. Let's focus on fundamental patterns. For me, there are two incredibly surprising facts about primes that can serve as a starting point. Of course, one or both may not be surprising to you. First, each positive number is characterized by a unique combination of primes.
If I take any set of primes (for example $2,3,5$) at a specific power (for this example, we'll choose the power of $1$), then there is ONLY one number equal to their product. In this case, $30$. This property is called unique factorization. The natural numbers are characterized by unique factorization. If there is a prime that divides one but not the other number, they are not equal. If there is a power of a prime that divides one but not the other, they are not equal. From this perspective, they provide an opportunity to simplify reasoning about very large numbers. If I have two very complicated equations which I want to compare, I can quickly see that they are not equal if a prime divides one but does not the other. For example, I can say without a doubt for all integer values of $x$ and $y$, the following will never be equal:
$$4^x \ne 7^y$$
I mentioned in a previous post that natural numbers are just one of many types of numbers. One of the most surprising facts for me is that not all number systems are characterized by unique factorization. In other words, there are numbers where they are products of different primes and yet they are still equal. With our intuitions about the concept of number from the whole numbers and the integers, this may seem impossible. If don't believe me, you can check it out for yourself. For example, not all quadratic integers are characterized by unique factorization. Even the great genius Leonhard Euler (pronounced Oiler) was not beyond making a bad assumption about unique factorization. If you are interested, I provide the details of his mistake here.
Unique factorization is such as an important properties of integers that the theorem that establishes unique factorization is called the Fundamental Theorem of Arithmetic.
In my next blog post, I will walk through a simple proof of this fundamental theorem.
No comments:
Post a Comment