# Probability and number theory, part II

In this post, we will explore the following question: If we choose two integers uniformly at random, what is the probability that they are relatively prime?

We start with a preliminary result. The Riemann zeta function, $$\zeta(s)$$, is ubiquitous in number theory. Although the most interesting version of it is the complex-valued one, today we only need the real version. It is defined as follows: for any real number $$s$$ greater than $$1,$$

$$\zeta(s) = \displaystyle\sum_{n=1}^{\infty} n^{-s}$$.

The Euler product  for the zeta function is the following alternative expression:

$$\zeta(s) = \displaystyle\prod_{p} \frac{1}{1 – p^{-s}},$$

where the product is taken over every prime $$p$$. To see why this formula is true, we start with the right-hand side and use a geometric series expansion to obtain

$$\displaystyle\prod_{p}\frac{1}{1-p^{-s}}=\displaystyle\prod_{p}(1+p^{-s}+p^{-2s}+\cdots).$$

By the Fundamental Theorem of Arithmetic, every positive integer can be expressed as a unique product of primes, up to order. (We consider $$1$$ to be the product of no primes; i.e., the empty product.) Thus, there is a one-to-one correspondence between the terms in the sum $$\sum_{n=1}^{\infty} n^{-s}$$ and the terms in the expansion of the product $$\prod_{p}(1+p^{-s}+p^{-2s}+\cdots).$$ Hence,

$$\displaystyle\prod_{p}\frac{1}{1-p^{-s}}=\displaystyle\sum_{n=1}^{\infty}n^{-s}=\zeta(s).$$

Now back to our original problem! Suppose we choose $$a, b \in \mathbb{Z}$$ uniformly at random. Fix an arbitrary prime $$p$$. The probability that both $$a$$ and $$b$$ are divisible by $$p$$ is $$\left(\frac{1}{p}\right)\left(\frac{1}{p}\right) = p^{-2}$$. Hence, the probability that they are not both divisible by $$p$$ is $$1 – p^{-2}$$.

The condition that $$a$$ and $$b$$ are relatively prime is equivalent to the condition that, for every prime $$p$$, $$a$$ and $$b$$ are not both divisible by $$p$$. Furthermore, for distinct primes $$p$$ and $$q$$, the events that $$a$$ and $$b$$ are not both divisible by $$p$$ and $$a$$ and $$b$$ are not both divisible by $$q$$ are mutually independent. (In fact, more precisely, the events that $$a$$ and $$b$$ are not both divisible by $$m$$ and $$a$$ and $$b$$ are not both divisible by $$n$$, for relatively prime integers $$m$$ and $$n$$, are mutually independent.)

Thus, the probability that $$a$$ and $$b$$ are relatively prime is equal to

$$\displaystyle\prod_{p}(1-p^{-2}),$$

where the product is taken over every prime $$p$$. But

$$\displaystyle\prod_{p}(1-p^{-2}) = \displaystyle\prod_{p}(\frac{1}{1-p^{-2}})^{-1}=(\displaystyle\prod_{p}\frac{1}{1-p^{-2}})^{-1} = \frac{1}{\zeta(2)}.$$

Hence the answer is $$\frac{1}{\zeta(2)}\approx 0.608. \, \spadesuit$$

The closed-form expression for $$\zeta(2)$$ is actually well-known (it equals $$\frac{\pi^{2}}{6})$$, but that’s another story for another day. The result also generalizes to more than two integers, a nice exercise for the reader.