Long-time Aperiodical muse David Cushing has made a bet with us that he can give us an interesting post every Friday for the next ten weeks. Every week that he sends a post, we buy him a bar of chocolate. Every week that he doesn’t send us a post, he buys us a bar of chocolate. For his first trick, David is going to do some unnatural things with the natural numbers.

The greatest common divisor (gcd) of two or more integers is the greatest integer that evenly divides those integers. For example, the gcd of $8$ and $12$ is $4$ (usually written as $\gcd(8,12)=4$). Two integers are called coprime (or “relatively prime”) if their gcd is equal to $1$.

A reasonable question to ask is,

Given two randomly chosen integers $a$ and $b$, what is the probability that $\gcd(a,b)=1$?

“Randomly chosen integers” is a bit of a dodgy term but we’ll just ignore that and hope for the best.

If no prime divides $n$, then $n=1$, by the fundamental theorem of arithmetic. So we want to find the probability that no prime divides $\gcd(a,b)$. Let $a$ and $b$ be two randomly chosen integers and $p$ a fixed prime. If $p$ divides both $a$ and $b$ then $\gcd(a,b)\geq p$. We are interested in the probability that this does not occur for any $p$.

Now I need to say what I mean by “randomly chosen”. It’s very handwavey, but we will calculate the probability for an integer chosen uniformly at random between $1$ and $N$, and then let $N$ tend to infinity. We won’t actually do that, but that’s what we’re thinking of.

Every $p$^th integer is divisible by $p$, so the probability that $p$ divides $a$ and $b$ is $\frac{1}{p^{2}}$, and the probability that it divides at most one of $a$ or $b$ is $1-\frac{1}{p^{2}}$. That’s a good start, but what we want is this probability over all primes. The probabilities for each prime are independent of each other, so you can just multiply them all together. Therefore the probability that $\gcd(a,b)=1$ is

\[ \Pr \left( \gcd(a,b) = 1 \right) = \prod_{p \textrm{ prime}} \left( 1 – \frac{1}{p^2} \right). \]

We now have the problem of evaluating this number. For those in the know, our expression looks pretty darn close to the definition of the Riemann zeta function:

\[ \zeta(s) =\prod_{p \textrm{ prime}} \left( 1 – \frac{1}{p^s} \right)^{-1} = \sum_{n=1}^{\infty} n^{-s}. \]

(We used the Euler product formula to relate the product we had with the usual definition of the zeta function, which is a sum.)

By comparing the two equations, we can see that $\Pr( \gcd(a,b) = 1 ) = \frac{1}{\zeta(2)}$. Thankfully, $\zeta(2)$ is simply the sum of the reciprocals of the square numbers, which we know is $\frac{\pi^2}{6}$ ((This infinite sum is the subject of the Basel problem, solved by Euler in 1735)). Therefore the probability that two randomly chosen integers are coprime is the reciprocal of that: $\frac{6}{\pi^2}$. So we are done!

\[ \Pr( \gcd(a,b) = 1) = \frac{6}{\pi^2} \approx 0.6079 \]

Well, sort of. Now that we know the probability the gcd of two randomly chosen integers is $1$, why not ask a few more general questions? What is the probability that the gcd of two randomly chosen integers is a prime number $p$? More generally, what is the probability that the gcd of two randomly chosen integers is some $k \in\mathbb{N}$, and what’s the probability that it’s any prime?

First of all, what’s the probability that $\gcd(a,b)$ is a prime $p$? That means:

• $p$ divides both $a$ and $b$
• $p^2$, and any other prime, only divide at most one of $a$ and $b$.

As we said before, $\Pr(p \mid \gcd(a,b)) = \frac{1}{p^2}$. We want to exclude the cases when $p^2$ divides both $a$ and $b$, which happens $\frac{1}{p^4}$ of the time. For any other prime $q$, we want the same thing as before: $\Pr(q \nmid \gcd(a,b)) = 1 – \frac{1}{q^2}$. So, putting it all together, we have:

\begin{align} \Pr( \gcd(a,b) = p ) &= \left( \frac{1}{p^2} – \frac{1}{p^4} \right) \prod_{q \neq p \textrm{ prime}} \left( 1 – \frac{1}{q^2} \right) \\ &= \frac{1}{p^2} \left(1 – \frac{1}{p^2} \right) \prod_{q \neq p \textrm{ prime}} \left( 1 – \frac{1}{q^2} \right) \\ &= \frac{1}{p^2} \prod_{q \textrm{ prime}} \left( 1 – \frac{1}{q^2} \right) \\ &= \frac{6}{p^2\pi^2}.  \end{align}

Next, we can apply a similar argument to find the probability that $\gcd(a,b) = p^n$. $p^n$ divides both numbers $\frac{1}{\left( p^n \right)^2}$ of the time, and we need to exclude the case where $p^{n+1}$ divides both numbers, which happens $\frac{1}{\left( p^{n+1} \right)^2}$ of the time. Like last time, we can take a factor of $\frac{1}{p^{2n}}$ out of this, to get:

\begin{align} \Pr( \gcd(a,b) = p^n ) &= \frac{1}{p^{2n}} \prod_{q \textrm{ prime}} \left( 1 – \frac{1}{q^2} \right) \\ &= \frac{6}{\left( p^n \right)^2\pi^2} \end{align}

It should be clear that you can take a couple of steps from here to derive that, for any $k \in \mathbb{N}$,

\[ \Pr( \gcd(a,b) = k ) = \frac{6}{k^2 \pi^2} \]

So what’s the probability that the gcd of two randomly chosen integers is any prime? Well, that’s simply

\begin{align} \sum_{p \textrm{ prime}} \Pr(\gcd(a,b)=p) &= \sum_{p \textrm{ prime}} \frac{6}{p^2 \pi^2} \\ &= \frac{6}{\pi^2} \cdot \sum_{p \textrm{ prime}} \frac{1}{p^2} \end{align}

To proceed any further we need to evaluate the sum of the reciprocals of the squares of the primes. When we did that with all the natural numbers, we used $\zeta(2)$. It turns out that there’s a related function which sums just over the primes, called the prime zeta function:

\[ P(s)=\sum_{p \textrm{ prime}} p^{-s}. \]

Replacing our sum with $P(2)$, we get:

\[  \Pr(\gcd(a,b) \textrm{ prime}) = \frac{6}{\pi^2} P(2) \approx \frac{6}{\pi^{2}} \times 0.45224 \approx 0.2749 \approx\frac{1}{4}. \]

So about a quarter.

Let’s end with one more generalisation. Let’s say we have 3 randomly chosen integers. No, scrap that. Let’s say we have 4 randomly chosen integers. No, that’s still not right… I know – let’s say we have $n$ randomly chosen integers!

Using similar arguments as above we can get that the probability of the gcd of $n$ integers chosen at random to be prime is \[ \frac{P(n)}{\zeta(n)}.\]

A nice simple(ish) answer and we are all done.

References

Riemann zeta function

Proof of the Euler product formula for the Riemann zeta function

Prime zeta function

There are three different proofs that $\sum_{n} \frac{1}{n^2} = \frac{\pi^2}{6}$ in Proofs from THE BOOK by Martin Aigner and Günter Ziegler. This was known as the Basel problem. Some more history is given in the comprehensive historical survey The Ubiquitous π by Dario Castellanos.

The Wolfram MathWorld page on “relatively prime” contains the excellent observation that $\frac{6}{\pi^2}$ is the fraction of points in the 2d lattice that you can see when standing at the origin. It also gives probabilities for pairs of numbers chosen from a few different principal ideal domains.

“On the distribution of the greatest common divisor” by Persi Diaconis and Paul Erdős does all this rigorously, with error terms and everything.