# The probability of coprimality

A famous result: Two positive integers chosen at random will be coprime with probability ${6/\pi^2}$.

One has to say what one means by this, since there is no uniform distribution on the positive integers. What we mean is that if we choose ${x}$ and ${y}$ uniformly and independently at random from the integers ${\{1,\ldots,N\}}$, then ${x}$ and ${y}$ will be coprime with probability tending to ${6/\pi^2}$ as ${N\rightarrow\infty}$.

Here is one classic proof: Consider the points ${(x,y)\in\{1,\ldots,N\}^2}$ such that ${\gcd(x,y)=1}$. If we scale this picture by ${M}$, we will have exactly the points ${(X,Y)\in\{1,\ldots,MN\}^2}$ such that ${\gcd(X,Y)=M}$. Therefore, whatever the limiting probability ${P}$ of being coprime is, the probability of having ${\gcd = M}$ is exactly ${P/M^2}$. The law of total probability then implies

$\displaystyle 1 = \lim_{N\rightarrow\infty}\mathbf{P}(\gcd(x,y)\in\mathbf{N}) = P \sum_{M=1} \frac{1}{M^2} = P\,\zeta(2).$

Another way of imagining a random element on a noncompact group ${G}$ is to look at the profinite completion ${\hat{G}}$, which is always compact so always possesses a uniform distribution. Now by the Chinese Remainder Theorem,

$\displaystyle \hat{\mathbf{Z}} = \prod_p \mathbf{Z}_p,$

so choosing an element at random from ${\hat{\mathbf{Z}}}$ is the same as choosing an element at random from ${\mathbf{Z}_p}$ for each ${p}$. The probability that a random element of ${\mathbf{Z}_p}$ is divisible by ${p}$ is precisely ${1/p}$, so the probably that two elements from ${\hat{\mathbf{Z}}}$ are coprime is precisely

$\displaystyle \prod_p (1-1/p^2) = 1/\zeta(2).$

This does not imply the asymtotic result in ${\mathbf{Z}}$ mentioned above, but it is a nice way of thinking about it.

EDIT (28/4/12): As pointed out to me by Freddie Manners, the “classic proof” suggested above suffers from the fatal defect of not proving that the limit exists. Here is an alternative proof which does prove that the limit exists. More generally, let ${d>1}$ and consider positive integers ${x_1,\ldots,x_d\leq X}$ chosen uniformly at random. Let ${G(X)}$ be the number of ${(x_1,\ldots,x_d)\in[1,X]^d}$ such that ${\gcd(x_1,\ldots,x_d)=1}$, and observe that the number of ${(x_1,\ldots,x_d)\in[1,X]^d}$ such that ${\gcd(x_1,\ldots,x_d) = n}$ is precisely ${G(X/n)}$. Then

$\displaystyle \lfloor X\rfloor^d = \sum_{n\geq1} G(X/n)$

for all ${X}$. Inverting this relationship,

$\displaystyle G(X) = \sum_{n\geq1} \mu(n) \lfloor X/n\rfloor^d.$

Thus, the probability that ${d}$ randomly and uniformly chosen integers ${x_1,\ldots,x_d\leq X}$ are all coprime is exactly

$\displaystyle P(X) = \sum_{n\geq1} \mu(n) \left(\frac{\lfloor X/n\rfloor}{\lfloor X\rfloor}\right)^d.$

The ${n}$th term here is bounded by ${n^{-d}}$, so by the dominated convergence theorem ${P(X)\rightarrow\sum_{n\geq1} \mu(n) n^{-d} = \zeta(d)^{-1}}$.

# Volume of the $n$-ball

The following is a simple and beautiful proof, shown to me to my great delight while I was in high school, that the ${n}$-ball of radius ${r}$ has ${n}$-volume

$\displaystyle \frac{\pi^{n/2} r^n}{\Gamma(\frac{n}{2}+1)}$

Although I expect most readers will know it, I believe that everybody should see it. I don’t know the history of it, and would be interested in learning.

Suppose that the ${n}$-ball ${B^n}$ of radius ${1}$ has ${n}$-volume ${V_n(1)}$. Then, by considering linear transformations, the ${n}$-ball ${rB^n}$ of radius ${r}$ has ${n}$-volume ${V_n(r) = V_n(1) r^n}$. Moreover, differentiating this with respect to ${r}$ should produce the surface ${(n-1)}$-volume of the ${(n-1)}$-sphere ${S^{n-1} = \partial B^n}$: thus we expect ${\text{vol}^{(n-1)}(S^{n-1}) = V_n(1) n r^{n-1}}$.

Now consider the integral

$\displaystyle I = \int_{\mathbf{R}^n} e^{-\pi|x|^2}\,dx.$

We will compute ${I}$ in two different ways. On the one hand,

$\displaystyle I = \int_{-\infty}^{+\infty}\cdots\int_{-\infty}^{+\infty} e^{-\pi x_1^2 -\cdots - \pi x_n^2}\,dx_1\cdots dx_n = \left(\int_{-\infty}^{+\infty} e^{-\pi x^2}\,dx\right)^n = 1.$

On the other hand, the form of ${I}$ suggests introducing a radial coordinate ${r=|x|}$. Computing this way,

$\displaystyle I = \int_0^\infty e^{-\pi r^2} (V_n(1) n r^{n-1})\,dr = \frac{n V_n(1)}{\pi^{n/2}} \int_0^\infty e^{-t^2} t^{n-1}\, dt\qquad\quad$

$\displaystyle \qquad\quad= \frac{n V_n(1)}{2 \pi^{n/2}} \int_0^\infty e^{-s} s^{n/2-1}\,ds = \frac{n V_n(1)}{2 \pi^{n/2}} \Gamma(n/2) = \frac{V_n(1)\Gamma(n/2+1)}{\pi^{n/2}}.$