首页 > 技术相关 > 任意两个自然数互质的概率?

任意两个自然数互质的概率?

2013年7月25日 发表评论 阅读评论

试问:任取两个自然数,它们互质的概率是多少?即以等概率取两个自然数 \( x, y \in \{1,2,\ldots,n\}\),令 \( P_2(n)\) 是 \(x\)、\(y\) 互质的概率,求 \(\lim_{n\to \infty} P_2(n)\) 。

一个经典的不甚严格的证明是这样的:

设 \(d\) 是任意正整数,则一个整数可以被 \(d\) 整除的概率就是 \(1/d\) —— 这很显然嘛,每过 \(d\) 个数就会出现一个 \(d\) 的倍数。 那么如果 \(x\)、\(y\) 的最大公约数为 \(d\),就意味着 \(x\) 和 \(y\) 可以同时被 \(d\) 整除,且 \(x/d\) 和 \(y/d\) 互质,因此 \(x\)、\(y\) 的最大公约数为 \(d\) 的概率就是 \(P/d^2\)。既然任意两个数都有最大公约数,取遍 \(d\) 所有情况后,其概率之和应为 1,即
\[
\sum_{d=1}^{\infty} \frac{P}{d^2} = 1
\]

因此
\[
P = \left(\sum_{d=1}^{\infty} \frac{1}{d^2} \right)^{-1} = \frac{1}{\zeta(2)} = \left(\frac{\pi^2}{6}\right) ^{-1} = \frac{6}{\pi^2}.
\]

其中 \(\zeta\) 代表 Riemann-Zeta 函数
\[
\zeta(s) =
\sum_{n=1}^\infty n^{-s} =
\frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \cdots
\]

这个求和是大家所熟知的一个数论上的著名结论,不熟悉的同学可以参考巴塞尔问题,它最早是由欧拉证明的。

易知 \(k\) 个随机自然数互质的概率是
\[
\lim_{n\to\infty} P_k(n) = \frac{1}{\zeta(k)}
\]

另外一个思路是这样的:[1]

设 \(p\) 是一个质数,则两个任取的自然数 \(x\)、\(y\) 同时被 \(p\) 整除的概率就是 \(1/p^2\)。于是若对所有的 \(p\),\(x\) 和 \(y\) 均不同时被 \(p\) 整除,其概率就是

\[
\prod_p \left(1-\frac{1}{p^2}\right) = \left( \prod_p \frac{1}{1-p^2} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}.
\]

这个乘积是欧拉乘积中 \(a(n)=1\) 的情况。这两种方法的结论是一样的。

如果把这个概率用到同一个整数上,就得到了另一个相关的问题:一个整数不含平方因子的概率是多少?答案也是 \(6 / \pi^2\)。

更严格的证明可以参考 [2] 中的定理 332。

[1] Coprime – Probabilities. (n.d.). In Wikipedia. Retrieved July 25, 2013, from http://en.wikipedia.org/wiki/Coprime#Probabilities.
[2] Hardy, G. Godfrey Harold, and Edward M. Wright. An introduction to the theory of numbers. Oxford University Press, 1979.

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

%d 博主赞过: