浅谈两正整数互质概率

· · 算法·理论

题目

证明：在正整数集中任意选取两个数，这两数互质概率为 \frac{6}{\pi^2}。

证明

已知素数序列 \{p_i\}，下标从 1 开始。

已知两数 a，b。
设 p_i \mid a 的概率为 P(a_{p_i})，p_i \mid b 的概率为 P(b_{p_i})。
易得 P(a_{p_i})=P(b_{p_i})=\frac{1}{p_i}。
所以 a 和 b 都不含有 p_i 这个因数的概率 P(C_i) 为 P(a_{p_i}) \times P(b_{p_i})=1-\frac{1}{{p_i}^2}。
以上我们考虑了一个素数的情况。

容易得出，对于每一个 p_i，事件 C_i 是相互独立的，所以 a，b 两数互质的概率为

\prod_{i=1}^\infty P(C_i)=\prod_{i=1}^\infty \left( 1-\frac{1}{p_i^2} \right)=\frac{1}{\zeta \left(2 \right)}=\frac{1}{\frac{\pi^2}{6}}=\frac{6}{\pi^2}

证毕。

最后一步看不懂？其实我这个初二牲也看不懂。
其实最后一步应用了欧拉乘积公式。
至于如何计算 \zeta \left(2 \right)，参见巴塞尔问题。

拜谢各位大佬，拜谢管理员通过。这不会成为某些毒瘤出题的idea吧！

END.