问题

从正整数 1~N 中任意取两数 m、n,设 P 为 m/n 可约分的概率,问 N→∞ 时,P为多少?

回答
这道题很有意思,我们来一起把它掰开了揉碎了聊聊。问题是这样的:从正整数 1 到 N 中,我们随机选取两个不同的数 m 和 n。那么,m 除以 n(或者 n 除以 m,这其实不影响结果)能够约分,也就是 m 和 n 有大于 1 的公因数的概率是多少?最后,我们看当 N 无穷大的时候,这个概率趋向于多少。

先说结论:当 N → ∞ 时,m/n 可约分的概率是 1 6/π²。

是不是有点意外?为什么一个简单的概率问题会涉及到 π?这正是数论的魅力所在,我们一步步来揭示这个答案的由来。

什么是“可约分”?

首先,我们得明确“可约分”的意思。如果两个整数 m 和 n 有大于 1 的公因数,那么它们就是“可约分”的。换句话说,m 和 n 存在一个整数 d > 1,使得 d 同时是 m 的约数和 n 的约数。

举个例子:
6 和 9 可以约分,因为它们都有公因数 3。 6/9 = 2/3。
7 和 10 不可以约分,因为它们唯一的公因数是 1。

那么,m 和 n 不可约分,等价于什么呢?这就要引出我们接下来的核心概念了。

互质:不可约分的核心

如果两个数 m 和 n 除了 1 之外没有其他公因数,我们就说它们是互质的。m 和 n 可约分就等价于它们不互质。

所以,问题就转化成了:从 1 到 N 中随机选取两个不同的数 m 和 n,它们不互质的概率是多少?或者说,它们互质的概率是多少?如果能算出它们互质的概率 P_互质,那么可约分的概率就是 1 P_互质。

什么时候两个数是互质的?

数论里有一个非常重要的结论,叫做欧拉积公式或黎曼猜想的早期形式,它告诉我们两个随机选取的正整数互质的概率是 6/π²。这个结果非常深刻,而且它并不依赖于我们选择的范围 N 有多大,只要这个范围足够大,近似就成立。

我们先不直接去证明这个 6/π² 的结论,因为它涉及一些稍微高深的数论知识。我们先从一个更直观的角度去理解它。

尝试理解互质概率的来源

想象一下,我们现在不从 1 到 N 中选取,而是从所有正整数中随机选取两个数。怎么才算随机选取两个数呢?这本身就有点棘手,因为正整数集是无限的。但我们可以从概率的角度来思考。

两个数 m 和 n 互质,意味着它们没有共同的质因数。一个质数 p(比如 2, 3, 5, 7, 11, ...)会不会是 m 和 n 的公因数呢?

考虑一个质数 p。
m 不能被 p 整除的概率是 (p1)/p。
n 不能被 p 整除的概率也是 (p1)/p。

那么,m 和 n 都不能被 p 整除的概率是多少?如果 m 和 n 的选取是独立的(在非常大的范围内选取时,这种独立性近似成立),那么这个概率就是 ((p1)/p) ((p1)/p) = ((p1)/p)²。

m 和 n 至少有一个能被 p 整除(也就是它们有公因数 p)的概率,就是 1 ((p1)/p)²。

两个数不互质,是因为它们至少有一个质因数是公因数。也就是说,存在某个质数 p,p 同时整除 m 和 n。

两个数互质,则意味着对于所有质数 p,p 都不能同时整除 m 和 n。

所以,它们互质的概率 P_互质 可以看作是:
P_互质 = P(2不整除m和n) P(3不整除m和n) P(5不整除m和n) ...

这里的“P(p不整除m和n)”是指对于一个给定的质数 p,选取的两个数 m 和 n 都不能被 p 整除的概率。我们刚才算出来,这个概率是 ((p1)/p)²。

所以,理论上(这里是在近似和直觉上):
P_互质 ≈ (1 1/2²) (1 1/3²) (1 1/5²) (1 1/7²) ...

这个无穷乘积是不是有点眼熟?它正是欧拉乘积公式与黎曼 zeta 函数 η(s) = Σ(1/n^s) 的关系:

1 / η(s) = Π (1 1/p^s)^(1) (对所有质数 p)

当 s=2 时,我们有:
1 / η(2) = Π (1 1/p²) ^(1)

将这个公式与我们上面互质概率的直觉形式对比一下:
P_互质 ≈ Π (1 1/p²) (对所有质数 p)

所以,P_互质 ≈ 1 / Π (1 1/p²)^(1) = 1 / η(2)

而黎曼 zeta 函数在 s=2 处的值是著名的:
η(2) = Σ (1/n²) = 1/1² + 1/2² + 1/3² + 1/4² + ... = π²/6

哇哦!所以 P_互质 ≈ 1 / (π²/6) = 6/π²。

这里的推导是基于“随机选取两个数互质的概率是 6/π²”这个已知事实的直觉理解。

回到“1 到 N 中”的问题

现在我们把目光收回到从 1 到 N 中选取两个数的情况。当 N 很大时,从 1 到 N 中随机选取两个数,其行为非常接近于从所有正整数中随机选取两个数。因为大数定律和概率的收敛性,这种近似是非常好的。

我们来更严谨一点考虑:
从 1 到 N 中选取两个不同的数 m 和 n,一共有 N(N1)/2 种组合。
我们想要计算的是,有多少对 (m, n) 使得 gcd(m, n) > 1。

这个直接计数会非常复杂。所以我们反过来计算互质的对数。
有多少对 (m, n) 使得 gcd(m, n) = 1?

这个问题的答案与前面提到的欧拉乘积公式紧密相关。 实际上,从 1 到 N 中随机选取两个数 m 和 n,它们互质的概率就是 6/π²。

为什么是 6/π²?一个更“基础”的视角

我们可以换个角度来理解这个 6/π²。

考虑一个固定的正整数 d > 1。有多少对 (m, n) 其中 1 ≤ m, n ≤ N 且 gcd(m, n) = d?
要使 gcd(m, n) = d,那么 m 和 n 都必须是 d 的倍数,并且 m/d 和 n/d 是互质的。
设 m = d m',n = d n'。
那么 1 ≤ d m' ≤ N => 1 ≤ m' ≤ N/d
同理 1 ≤ n' ≤ N/d
并且 gcd(m', n') = 1。

所以,要计算 gcd(m, n) = d 的对数,就相当于计算从 1 到 ⌊N/d⌋ 的范围内选取两个数 m' 和 n'(允许相等,我们稍后再处理重复和不同的问题),它们互质的对数。

我们知道,从 1 到 K 中选取两个数(允许相等)互质的概率是 6/π²。
所以,大概有 (N/d)² (6/π²) 对数(m', n')满足 gcd(m', n') = 1。
这意味着,大概有 (N/d)² (6/π²) 对数 (m, n) 满足 gcd(m, n) = d。

现在,我们来考虑有多少对 (m, n) 使得 gcd(m, n) > 1。
这等于 Σ [所有 d>1 使得 d 同时整除 m 和 n 的对数]。
但是直接加起来会重复计算。

一个更常用的方法是利用莫比乌斯反演或者直接计算互质对。

从 1 到 N 中,互质的对 (m, n) 的数量大约是:
2 Σ_{n=1}^{N} φ(n) 1 (其中 φ(n) 是欧拉函数,表示小于等于 n 且与 n 互质的正整数的个数)。
当 N 很大时,Σ_{n=1}^{N} φ(n) ≈ (3/π²) N²。
所以互质的对数大约是 2 (3/π²) N² = (6/π²) N²。

由于总的选法有 N² 种(如果我们允许 m=n,或者不区分 m,n 的顺序),所以互质的概率就是 ((6/π²) N²) / N² = 6/π²。

如果我们在题目中强调“取两数 m、n”,通常意味着它们是不同的。
从 1 到 N 中选取两个不同的数,总共有 N(N1) 对有序对 (m, n)。
其中 m 和 n 互质的对数大约是 N² (6/π²)。

因此,互质的概率 P_互质 ≈ (N² 6/π²) / N² = 6/π²。

所以,m/n 可约分的概率 P = 1 P_互质 ≈ 1 6/π²。

总结一下这个过程

1. 理解问题核心: “可约分”意味着两个数有大于 1 的公因数,也就是它们“不互质”。所以我们关注的是它们“互质”的概率。
2. 直觉上的理解: 两个数互质意味着它们没有共同的质因数。我们可以从每个质数 p 的角度去考虑,p 同时整除 m 和 n 的概率有多大。
3. 质数 p 的贡献: 对于一个质数 p,m 和 n 都不能被 p 整除的概率是 (1 1/p)²。那么至少有一个被 p 整除的概率是 1 (1 1/p)²。
4. 无穷乘积: 两个数互质,意味着对于所有质数 p,p 都不能同时整除它们。所以互质的概率可以看作是所有质数 p 下“p 不能同时整除 m 和 n”的概率的乘积,即 Π (1 1/p²)。
5. 欧拉乘积公式的关联: 这个无穷乘积正好是黎曼 zeta 函数 η(2) 的倒数。
6. 黎曼 zeta 函数: η(2) = Σ (1/n²) = π²/6。
7. 得出概率: 因此,两个随机选取的正整数互质的概率是 1 / η(2) = 6/π²。
8. N→∞ 的近似: 当我们从 1 到 N 中选取时,只要 N 足够大,这种随机性就近似于从所有正整数中选取。因此,互质的概率近似为 6/π²。
9. 最终答案: m/n 可约分的概率 P = 1 P_互质 ≈ 1 6/π²。

所以,当你从 1 到 N 的整数中随意挑出两个数,当 N 变得越来越大时,它们是可以约分的(有大于 1 的公因数)的概率会越来越接近于 1 6/π²。这个结果非常美妙,它将一个简单的概率问题与 π 和数论的深层结构联系了起来。

π² ≈ 9.8696
6/π² ≈ 0.6079
1 6/π² ≈ 0.3921

这意味着,当 N 非常大的时候,你任意挑出两个数,它们是不能约分的(互质)的概率大约是 60.8%,而它们是可以约分的概率大约是 39.2%。

这个结果有点违反直觉,很多人会觉得两个数不能约分(互质)的概率应该很小,但实际上恰恰相反,互质的概率是大于不是互质的概率的。这说明了质数在数论中的“力量”是多么的普遍和强大。

网友意见

user avatar

简单答一下,欧拉函数 表示1-n之间与n互质的数的个数,显然修复掉m和n相等时的那一点点差异(区间足够大时可以忽略不计),就可以转化为求 (n是1-100,或者1-N之间的均匀分布)

接下来我们有

这里p是质数,也就是对n的所有质因子求乘积。把求乘积下面的条件改写为示性函数,可以变成对所有质数求乘积:

I(p|n)在p整除n时为1,否则为0。

对于任意整数a,当N足够大时,可以认为 ,同时对于不同的质数p1和p2,有

按照定义这说明事件 对于不同质数独立。

因此,可以使用独立事件的期望公式:

最后利用一顿解析数论的操作(见其他回答)可以得到结果为 ,注意这是两数互质的情况,可约则是

类似的话题

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有