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

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

• shreevatsa.wordpress.com/2008/11/07/… Commented May 15, 2012 at 20:03
• Answer on MathWorld, equation (1): mathworld.wolfram.com/RelativelyPrime.html Commented May 15, 2012 at 20:03
• This is pretty marginal, level-wise. Commented May 15, 2012 at 20:26
• A good question, but not a question of any research interest, as the answer can be found in entry-level Number Theory textbooks - and this website is for questions of research interest. Commented May 15, 2012 at 23:06
• The margin is too small to contain it. Commented May 16, 2012 at 1:16

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.
• ...... likewise $1/\zeta_K(n)$ is the probability that $n>1$ ideals or field elements have no common factor. This also lets you asymptotically count rational points up to a given height in projective space over $K$. Here's why I had to look up these references some years ago: arxiv.org/pdf/math/0104115v1.pdf Commented May 16, 2012 at 1:26
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).$$
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}$).