What is the probability that two randomly chosen integers have no prime factors in common? In honor of Pi Day, I’d like to explain the surprising answer: .
The hero of this story is Leonhard Euler, who worked out this astonishing connection between prime numbers and through a series of brilliant insights. In the spirit of Euler, I will be rather cavalier about issues of convergence and rigor here, focusing on the key underlying ideas.
Let the probability in question be denoted . Euler’s first observation is that if and are chosen at random, the probability that they are both even is , and so the probability that they are not both even is . Similarly, the probability that and are both divisible by 3 is , so the probability that they are not both divisible by 3 is . The probability that and are not both divisible by either 2 or 3 is therefore Continuing in this way, Euler finds that can be expressed as an infinite product over all primes:
Euler’s next step is to note that by the formula for the sum of a geometric series, and therefore we can rewrite our formula for as a formula for involving an infinite product of infinite sums:
Euler, in typically bold fashion, decides not to panic about all these infinities and just multiplies everything out term-by-term. He notices that the leading 1’s in each parenthetical expression multiply out to give 1, the together with all the other leading 1’s multiply out to give , and the together with all the other leading 1’s multiply out to give . In fact, Euler realizes that there is a unique way to obtain for each positive integer : use the prime factorization of to read off which terms to multiply together. For example, to obtain we choose from the first parenthetical expression, from the third, and 1’s from everywhere else. The terms which don’t involve choosing 1 all but finitely many times are neglible, according to Euler’s keen intuition (which is not hard to make precise with a bit of calculus that we’ll skip here). Therefore:
Now calculating the value of the infinite sum is a famous problem (often referred to as the Basel problem). Here’s how Euler solves it.
The Taylor series for is
The roots of are and so thinking of the Taylor series for as an “infinite polynomial”, Euler obtains the identity
Now the right-hand side can be simplified, using the difference of squares formula , as
Comparing coefficients of in both sides of the identity
Euler obtains which can be rearranged to give Therefore as claimed.
Rest in peace, Euler. And happy Pi Day to the rest of you!
- Keith Conrad points out that there is something amiss with the above Pi Pie. Can you figure out what it is?
- For a rigorous proof of the formula see for example Chapter 1 in these Trinity College lecture notes. To make the formula rigorous, one can apply the Weierstrass Factorization Theorem.
- For 13 other solutions to the Basel problem, see these notes by Robin Chapman.
- For a more rigorous proof that see e.g. Theorem 8.1 of these lecture notes by Fabian Pazuki. (The definition of the Weil height function on projective space shows that , which by Theorem 8.1 of loc. cit. is ) Note that this proof utilizes the Möbius inversion formula instead of Euler’s product formula