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}}$ .

The probability of coprimality

Published by Sean Eberhard

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Sean Eberhard

Leave a Reply Cancel reply