What is the probability that the GCD of $n$ naturals $\le m$ is 1?

135 Views Asked by At

What is the probability that the GCD of $n$ naturals $\le m$ is 1?

For example, if the there are $n=2$ numbers less than or equal to $m=2$, there are four combinations - {1,1},{1,2},{2,1},{2,2}. Only the last combination, {2,2}, has a GCD greater than 1. So with $n=2, m=2$, the probability is 3/4.

1

There are 1 best solutions below

3
On BEST ANSWER

(Note: it seems that I've used $k$ instead of $n$.)

This probability is given by function

$$C_k(m):=\frac1{m^k}\sum_{\substack{a_1,\dots,a_k\leq m\\\gcd(a_1,\dots,a_k)=1}}1$$

where the sum is extended to all the tuples $(a_1,\dots,a_k)$ with $a_i\leq m$ ($i=1,\dots,n$) that are relatively prime. One may prove that

$$C_k(m)\sim\frac1{\zeta(k)};$$

that is to say, this probability tends to $1/\zeta(k)$ as $k\to\infty$ (where $\zeta(k)$ is the Riemann zeta function.) In particular, for $k=2$, the "probability" (more precisely, the asymptotic density) that two randomly chosen integers are relative prime is $6/\pi^2$. The proof of this result would be as follows:

$$\begin{align*} C_2(m)&=\frac1{m^2}\sum_{a\leq m}\sum_{\substack{b\leq m\\(a,b)=1}}1 =\frac2{m^2}\left(\sum_{a\leq m}\sum_{\substack{b\leq a\\(a,b)=1}}1\right)-1 =\frac2{m^2}\sum_{a\leq m}\varphi(a)-1, \end{align*}$$

where $\varphi(a)$ is the Euler's totient function, that counts the number of relatively prime to $a$ that are $\leq a$. In the second equality we made use of the symmetry: summing the pairs $(a,b)$ of the square $a,b\leq m$ such that $\gcd(a,b)=1$ is the same as summing the pairs inside the lower triangle $a\leq m,b\leq a$ and the pairs inside the upper triangle $b\leq m,a\leq b$ that satisfies $\gcd(a,b)=1$ (minus the intersection, which consists of a single point.) Both quantities turn out to be the same because $(a,b)=1$ iff $(b,a)=1$.

Now, since $\varphi=\mu*N$, we have (if we write $a=dq$)

$$\begin{align*} \sum_{a\leq m}\sum_{d|a}\mu(a)\frac ad&=\sum_{d\leq m}\mu(d)\sum_{q\leq m/d}q\\ &=\sum_{d\leq m}\left(\frac{m^2\mu(d)}{2d^2}+O(m/d)\right)\\ &=\frac{m^2}{2}\sum_{d\geq1}\frac{\mu(d)}{d^2}+O\left(\sum_{d>m}\frac{m^2}{d^2}\right)+O(m\log(m)) \end{align*}$$

so $\sum_{a\leq k}\varphi(a)\sim Am^2/2$, where $A=\sum_{d\geq1}\mu(d)/d^2$. Therefore

$$\lim_{m\to\infty}C_2(m)=\lim_{m\to\infty}\frac2{m^2}\frac{m^2}{2}A=A.$$

Now we are left to find $A$. We note that

$$\sum_{d\geq1}\frac{\mu(d)}{d^2}\sum_{q\geq1}\frac1{q^2} =\sum_{d,q\geq1}\frac{\mu(d)}{(dq)^2},$$

so if we write $n=dq$, we can rewrite it as

$$\sum_{n\geq1}\frac1{n^2}\sum_{dq=n}\mu(d) =\sum_{n\geq1}\frac1{n^2}\sum_{d|n}\mu(d) =\sum_{n\geq1}\frac1{n^2}I(n)$$

where $I(n)$ is the identity under Dirchlet convolution (i.e., $I(1)=1$ and $I(n)=0$ otherwise.) Therefore

$$A\sum_{n\geq1}\frac1{n^2}=1$$

so $A=1/\zeta(2)=6/\pi^2$. A similar (but longer) argument shows that $C_k$ converges to $1/\zeta(k)$.