How often do coprime numbers appear?

Coprime numbers, also known as relatively prime numbers, are integers that do not share any prime factors, or equivalently having a greatest common divisor (GCD) of 1. Although the definition of coprime integers are originally for a pair of integers, it can be extended to any number of integers due to its associativity.

When I first learnt about coprime integers in a number theory course, there was a question that was not covered during the course, nor did it occur to me until recently: what is the probability of choosing a pair of coprime integers at random¹?

Hi Again, Pi

There turns out to be a definitive answer to this question with several well-established proofs, and it is quite an elegant one:

$$\frac{6}{\pi^2} = 0.6079271... \approx 61\%$$

Surprisingly, $\pi$ seems to appear out of nowhere in the answer, which makes this a topic that could make into 3Blue1Brown's "Why pi?" video series. However, this should look familiar to those who are familiar with the Basel problem, or the sum of reciprocals of perfect squares. In fact, they are very closely related.

A Straightforward Proof

There are several proofs of this result, including one by Dirichlet that has existed since all the way back to 1849, and one that involves a more advanced concept called lattice points (see Apostol's Introduction to Analytic Number Theory, Theorem 3.9), but there is actually a simpler, yet more insightful argument, presented by Simon Tiger, a budding prodigy mathematician.

He does not go for the usual brute-force, 'bottom-up' method of running through massive numbers of integer pair samples while checking for the coprimality of each pair and keeping track of the odds in order to see if the probability converges to a certain constant. Instead, he takes a 'top-down' approach by looking at the probability of a pair of integers having a greatest common divisor (GCD) of $2$ or above.

What does this mean? Suppose that we call the first number $x_1$ and the second number $x_2$. Let's start with $2$ as the target factor. For $x_1$ and $x_2$ to have an GCD of $2$, they must at least both be divisible by $2$. Since modular arithmetic tells us that we can group integers evenly based on their respective remainders after being divided by a certain factor, the probability of $x_1$ (resp. $x_2$) being divisible by $2$ (i.e. having remainder zero) is $\frac{1}{2}$.

Note that $2$ must be the highest common factor of $x_1$ and $x_2$, so if we divide both of them by $2$, they cannot share any other factor (except for $1$ of course). Note that this is exactly the definition of coprimality! In other words, we have obtained a pair of coprime integers (namely $\frac{x_1}{2}$ and $\frac{x_2}{2}$) through this procedure. What is the probability of finding such a pair? That's exactly what we're looking for; let's call that value $p$.

The key of the procedure just now is that it gives us an important characterisation of a pair of integers having a certain number as their GCD: they must both be divisible by said number, and after dividing them by that number, the new resulting pair must be coprime.

Why?

If $x_1$ and $x_2$ had other common factors greater than $1$ (say, $b$) after being divided by their GCD (denoted here as $a$), then $ab$, which is greater than $a$, should have been the GCD instead, leading to a contradiction.

What is the probability of finding an integer pair like this? The argument above tells us that it is the product of the probabilities, which represent the criteria that must be fulfilled simultaneously, that we obtained through the procedure, i.e. $\frac{1}{2} \cdot \frac{1}{2} \cdot p = \frac{p}{4}$.

At this stage, you may have figured out that this procedure can be repeated for every other integer factors. For $3$, we obtain $\frac{1}{3} \cdot \frac{1}{3} \cdot p = \frac{p}{9}$; for $4$, we obtain $\frac{p}{16}$, and so on. We can even deduce the general pattern: for a factor $k$, the probability of an integer pair having $k$ as their GCD is $\frac{p}{k^2}$. This general pattern even works for the case when $k = 1$, because an integer pair having $1$ as their GCD essentially means that they are coprime, so the corresponding probability is indeed $p$.

Now, we see how everything comes together which helps us to obtain the value of $p$ that we want. Note that any integer pair has the GCD of any number. This means that the probability of obtaining any integer pair among the sea of all integer pairs, which is clearly $1$, is equal to the sum of all probabilities of an integer pair having the GCD of any number, ranged over all integers! Rewriting this description into an algebraic equation, we obtain

$$\sum_{\substack{k = 1}}^{\infty}\frac{p}{k^2}=1.$$

Rearranging the variables a bit yields

$$p=\cfrac{1}{\sum_{\substack{k \in \mathbb{Z}_{>0}}}\frac{1}{k^2}}$$ $$\implies p=\cfrac{1}{\frac{\pi^2}{6}}=\frac{6}{\pi^2}.$$

In other words, the probability $p$ of a randomly chosen integer pair being coprime is the reciprocal of the sum of reciprocal of squares! That's where the Basel problem, i.e. the reason why $\pi$ shows up in the solution, plays a role!

Extension to $n$ integers

Another cool part of this argument is that it can be easily extended to an arbitrary number of randomly chosen integers, say, $n$ of them.

By investigating $n$ possible integers, say, $x_1,x_2,\ldots,x_n$ instead of just two like before, calculating the probability of these integers having a certain number $k$ as their GCD now involves multiplying $\frac{1}{k}$ for $n$ times in total, followed by multiplying $p$ at the end as before.

In a similar vein, we then obtain that

$$p=\frac{1}{\sum_{k \in \mathbb{Z}_{>0}}\frac{1}{k^n}}.$$

Does the denominator ring a bell? It is in fact the definition of the Riemann zeta function!

$$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}={\frac {1}{1^{s}}}+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+\cdots$$

Rather, for the special case of positive integers, it is more commonly known as the $p$-series.

It may be tempting to ask what the probability will become as the number of integers chosen 'tends to infinity'. It may even be more tempting to deduce from the general formula we just obtained to conclude that the answer should be $1$. However, this question is meaningless because there can be contradicting outcomes depending on what kind of infinite collections of integers we are considering. For instance, the probability is $0$ for all even numbers, but is $1$ for all positive integers; notice that both cases involve an infinite number of integers.

What if we consider a finite range of numbers and a finite number of choices instead? According to this paper, this probability seems to decrease as the number of choices increases, which is frankly an interesting result.

Other sources, further reading

• Zeta functions, statistical mechanics and Haar measure, by Qiaochu Yuan
• On the Probability That Two Random Integers Are Coprime, by Jing Lei and Joseph B. Kadane
• The Probability that Two Random Integers are Coprime, by Julien Bureaux and Nathanael Enriquez
• Probability of Coprimality section in the Wikipedia article on coprime integers
• What is the probability that $n$ integers chosen at random are coprime? on Mathematics StackExchange
• Probability that two random numbers are coprime is $6/\pi^2$ on Mathematics StackExchange
• The Probability that $k$ Positive Integers are Pairwise Relatively Prime, by László Tóth

Footnotes

1. Technically, it is impossible to choose a positive integer truly randomly such that each choice occurs with the same probability. However, we can still make formal mathematical definitions about such 'randomness' to suit our needs here; see here or here for more information. ↩