Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

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.

    
    
Answer on MathWorld, equation (1): mathworld.wolfram.com/RelativelyPrime.html –  Yoav Kallus May 15 '12 at 20:03
3  
This is pretty marginal, level-wise. –  Igor Rivin May 15 '12 at 20:26
5  
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. –  Gerry Myerson May 15 '12 at 23:06
4  
The margin is too small to contain it. –  Noam D. Elkies May 16 '12 at 1:16

3 Answers 3

up vote 17 down vote accepted

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.

share|improve this answer
2  
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)... –  Noam D. Elkies May 16 '12 at 1:24
1  
...... 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 –  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).$$

share|improve this answer

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

share|improve this answer

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