What is the probability that two numbers are relatively prime? - MathOverflow [closed]

What is the probability that two numbers are relatively prime?

2012-05-15T19:57:36Z

The basic question that I have is in the title, but let us make it more rigorous below.

Let $N={1, 2, ..., n}$, and put the (normalized) counting measure, $\mu_n$, on $N\times N$.

Let $\mathcal{S}_n= { (a, b)\in N\times N: gcd(a, b)=1}$

and $x_n=\mu_n(\mathcal{S}_n).$

Then what is the assymptotic behavior of $x_n$ as $n\rightarrow\infty$.

Answer by Qiaochu Yuan for What is the probability that two numbers are relatively prime?

2012-05-15T20:03:44Z

The probability is $\frac{6}{\pi^2} = \frac{1}{\zeta(2)}$. A sketch of a proof can be found in this blog post (actually I only show, more or less, that if the density exists it must be $\frac{6}{\pi^2}$).

Answer by Gjergji Zaimi for What is the probability that two numbers are relatively prime?

2012-05-15T20:14:15Z

The probability tends to $\frac{1}{\zeta(2)}=\frac{6}{\pi^2}$ as was mentioned by Qiaochu. This actually generalizes to arbitrary number fields, and is a less commonly known fact.

In fact in any number field, the probability that two ideals are relatively prime is given by $1/\zeta_K(2)$, where $\zeta_K$ is the Dedekind zeta function of the number field $K$. And is proven in a similar way to the classical result. Here is a reference: "The probability of relative primality of Gaussian integers". For example the analogous probability for Gaussian integers is $6/(\pi^2G)$ where $G=1-\frac{1}{3^2}+\frac{1}{5^2}+\cdots$ is the Catalan constant.

Answer by i707107 for What is the probability that two numbers are relatively prime?

2012-05-15T20:19:47Z

This is a very standard counting problem in analytic number theory. Here's a rigorous proof: It is enough to derive an asymptotic formula for $$\sum_{a,b\leq n, (a,b)=1} 1 $$ This is $$\sum_{a,b\leq n, d|a, d|b} \mu(d) $$ $$=\sum_{d\leq n} \mu(d)\sum_{k\leq n/d , l\leq n/d} 1$$ $$=\sum_{d\leq n} \mu(d) ((n/d)^2 + O(n/d) ) $$ $$=n^2\sum_{d\leq n} \mu(d)/d^2 + O(n\log n)$$ $$=n^2\sum_{d=1}^{\infty} \mu(d)/d^2 + O(n) + O(n\log n)$$. $$=n^2 6/\pi^2 + O(n\log n).$$