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


closed as too localized by Charles, Igor Rivin, Felipe Voloch, Gerry Myerson, Andy Putman May 16 '12 at 1:39

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.


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.

  • 2
    $\begingroup$ A reference for the general "less commonly known fact" is Schanuel, S.H.: Heights in number fields, Bull. Soc. Math. France 107 (1979), 433–449. It is true also using field elements in place of ideals. A function-field analogue was announced by Serre in Lectures on the Mordell-Weil Theorem (F. Vieweg & Sohn, Braunschweig 1989) and proved independently but in the same way by S.DiPippo (Spaces of Rational Functions on Curves Over Finite Fields, Ph.D. Thesis, Harvard, 1990) and D.Wan (Heights and Zeta Functions in Function Fields, in The Arithmetic of Function Fields (1992)... $\endgroup$ – Noam D. Elkies May 16 '12 at 1:24
  • 1
    $\begingroup$ ...... 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 $\endgroup$ – Noam D. Elkies May 16 '12 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}$).


Not the answer you're looking for? Browse other questions tagged or ask your own question.