Prime factors and π

Recall that a prime number is a natural number greater than 1 that is only divisible by 1 and itself. The first few prime numbers are 2, 3, 5, and 7.

The Fundamental Theorem of Arithmetic (FTA), which is perhaps the most crucial theorem in the branch of mathematics known as number theory, guarantees that every natural number greater than 1 can be expressed as a distinct product of prime numbers. This product is known as the number’s prime factorization or prime decomposition.

If you have a background in mathematics, the FTA will be familiar to you. However, it can be astonishing when first encountered—it truly is an astounding result!

There are infinitely many natural numbers, and each of them is either prime or can be factored into a unique product of primes. In this manner, prime numbers serve as the fundamental building blocks of our natural number system, just as various subatomic particles act as the fundamental building blocks of matter.

Since every natural number greater than 1 can be factored into a product of primes, we can start to observe relationships between certain numbers. For instance, every even number has at least one copy of 2 in its prime factorization. Here are a few examples:

\(\begin{align*} 4 &= 2 \cdot 2\\ 10 &= 2 \cdot 5\\ 24 &= 2 \cdot 2 \cdot 2 \cdot 3 \end{align*}\)

The number 45 is odd, so its factorization does not contain a copy of 2:

\(45 = 3 \cdot 3 \cdot 5\)

But it does contain a copy of 5. So does the factorization for the number 10. So the numbers 10 and 45 share something in common, the prime number 5.

Some pairs of numbers have no prime factors in common. This is the case for 30 and 77 from the video:

\(\begin{align*} 30 &= 2 \cdot 3 \cdot 5\\ 77 &= 7 \cdot 11\\ \end{align*}\)

Mathematicians use the term coprime or relatively prime to describe pairs of numbers like this. The concept of coprimeness can be viewed as a kind of taxonomy for natural numbers. Two numbers are "related" if they share a common prime factor, while they are considered "unrelated", or coprime, if they do not share any prime factors.

How common are coprime pairs? Stated another way: if we randomly choose two natural numbers, what is the probability that they are coprime? It turns out that this probability is around 60%, and our good friend π shows up in the answer.

The following “proof” is informal and involves some hand-waving, but it conveys the basic idea.

What is the probability that a randomly selected natural number greater than 1 is divisible by 2? Since “half” of the natural numbers are even and half are odd, this probability is equal to:

\(\frac{1}{2}\)

Now, if we randomly select two natural numbers, what is the probability that both happen to be divisible by 2? We can think of this scenario as flipping a fair coin that has "divisible by 2" on one side and "not divisible by 2" on the other. Choosing two integers in a row that are divisible by 2 is like flipping the coin twice and getting "divisible by 2" both times. The probability of this happening is:

\(\left(\frac{1}{2}\right) \cdot \left(\frac{1}{2}\right) =\left(\frac{1}{2}\right)^2\)

The above probability is equal to .25. Therefore, the probability of at least one number not being divisible by 2 is the complement of this probability 1 - .25 or:

\( 1 - \left( \frac{1}{2} \right)^2\)

In other words, this is the probability that the two numbers do not share 2 as a common factor.

The insight is to realize that this logic works for any prime. For example, every third natural number is divisible by 3. So the probability that a random selected number is divisible by 3 is:

\(\frac{1}{3}\)

The probability that two randomly selected numbers are both divisible by 3 is:

\(\left(\frac{1}{3}\right) \cdot \left(\frac{1}{3}\right) =\left(\frac{1}{3}\right)^2\)

And therefore the probability that at least one of them is not divisible by 3, i.e. the numbers do not share 3 as a common factor, is:

\(1 - \left( \frac{1}{3} \right)^2\)

The probability that they do not share 5 as a common factor is:

\(1 - \left( \frac{1}{5} \right)^2\)

And so on.

According to probability theory, if multiple events are independent, then the probability of all of them happening simultaneously is equal to the product of their individual probabilities. Therefore, the probability that two numbers do not share any common factor of 2, 3, 5, 7, ... is equal to:

\(\left( 1 - \left( \frac{1}{2} \right)^2 \right) \cdot \left( 1 - \left( \frac{1}{3} \right)^2 \right) \cdot \left( 1 - \left( \frac{1}{5} \right)^2 \right) \cdot \left( 1 - \left( \frac{1}{7} \right)^2 \right) \cdot \; ...\)

This is an infinite product that ranges over all the prime numbers, and it is related to a very important function in mathematics known as the Riemann zeta function. The answer turns out to be:

\(\frac{6}{\pi^2} = .6079...\)

So pairs of “unrelated” coprime numbers are actually slightly more common than pairs of “related” or non-coprime numbers!

It's surprising that π appears in the solution to this probabilistic question about prime numbers. There is no reason to expect this from the outset, but as is often the case in mathematics, unanticipated connections emerge at every turn.