对于给定的一个不小于2的正整数n,随机选取两个小于或等于n的互异的正整数,记这两个正整数互质的概率为P(n).求当n无限大时,P(n)的极限.

Question

对于给定的一个不小于2的正整数n,随机选取两个小于或等于n的互异的正整数,记这两个正整数互质的概率为P(n).求当n无限大时,P(n)的极限.

Answer 1

记所取整数对的最大公约数为gcd.
n以内的p倍数共有[n/p]个,故素数p|gcd的对数共有[n/p]^2个,
那么gcd不含p的频率F(p)=(n^2-[n/p]^2)/n^2≈1-1/p^2.
整数对互质当且仅当g不含有小于n的任一素数,故互质概率P(n)≈∏(1-1/p^2).
由欧拉恒等式可知,当n→∞时,P(∞)=1/(1+1/2^2+1/3^2+…+1/k^2+…)=6/π^2.
注意：我们取整数对时并没有强调相异,相异性由后来的“g不含有小于n的任一素数”筛滤而得.