What is the probability that two numbers are relatively prime? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-24T02:56:20Z http://mathoverflow.net/feeds/question/97041 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97041/what-is-the-probability-that-two-numbers-are-relatively-prime What is the probability that two numbers are relatively prime? Owen Sizemore 2012-05-15T19:57:36Z 2012-05-15T20:19:47Z <p>The basic question that I have is in the title, but let us make it more rigorous below.</p> <p>Let $N={1, 2, ..., n}$, and put the (normalized) counting measure, $\mu_n$, on $N\times N$. </p> <p>Let $\mathcal{S}_n= { (a, b)\in N\times N: gcd(a, b)=1}$</p> <p>and $x_n=\mu_n(\mathcal{S}_n).$</p> <p>Then what is the assymptotic behavior of $x_n$ as $n\rightarrow\infty$.</p> http://mathoverflow.net/questions/97041/what-is-the-probability-that-two-numbers-are-relatively-prime/97042#97042 Answer by Qiaochu Yuan for What is the probability that two numbers are relatively prime? Qiaochu Yuan 2012-05-15T20:03:44Z 2012-05-15T20:03:44Z <p>The probability is $\frac{6}{\pi^2} = \frac{1}{\zeta(2)}$. A sketch of a proof can be found in <a href="http://qchu.wordpress.com/2010/11/09/zeta-functions-statistical-mechanics-and-haar-measure/" rel="nofollow">this blog post</a> (actually I only show, more or less, that if the density exists it must be $\frac{6}{\pi^2}$). </p> http://mathoverflow.net/questions/97041/what-is-the-probability-that-two-numbers-are-relatively-prime/97045#97045 Answer by Gjergji Zaimi for What is the probability that two numbers are relatively prime? Gjergji Zaimi 2012-05-15T20:14:15Z 2012-05-15T20:14:15Z <p>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. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Dedekind_zeta_function" rel="nofollow">Dedekind zeta function</a> of the number field $K$. And is proven in a similar way to the classical result. Here is a reference: <a href="http://www.springerlink.com/content/y826m64747254t87/" rel="nofollow">"The probability of relative primality of Gaussian integers"</a>. 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 <a href="http://en.wikipedia.org/wiki/Catalan_constant" rel="nofollow">Catalan constant</a>.</p> http://mathoverflow.net/questions/97041/what-is-the-probability-that-two-numbers-are-relatively-prime/97047#97047 Answer by i707107 for What is the probability that two numbers are relatively prime? i707107 2012-05-15T20:19:47Z 2012-05-15T20:19:47Z <p>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).$$ </p>