2010-01-06 2:08| 
26 Comments | 本文内容遵从 偶然读到一个非常帅的证明：用信息熵可以瞬间证明素数有无穷多个。这个证明比本 Blog 之前讲过的五种非主流证明 (282, 539, 1678) 看上去都要帅，并且更重要地，它道出了素数无穷多的根本原因：只有无穷多的素数，才有能力表达出如此丰富的自然数世界。
假设我们从所有不超过 n 的自然数中随机选取一个数 N ，并把它分解成质因数的乘积 N = P1^X1 * P2^X2 * ... * Pm^Xm，其中 m 是不超过 n 的素数的个数。注意到由于 2^Xi ≤ Pi^Xi ≤ N ≤ n 对所有 i 都成立，因此我们有 Xi ≤ log(n) 。真正帅的地方来了。考虑随机选取一个 N 带来的信息熵，我们有：
log(n) = H(N)
= H(X1, X2, ..., Xm)
≤ H(X1) + H(X2) + ... + H(Xm)
≤ log(log(n)+1) * m
上面的第一个等号是由信息熵的定义直接得出的。第二个等号是由唯一分解定理得到的：由于一个数可以唯一地分解为质因数的乘积，因此 N 和 (X1, X2, ..., Xm) 是一一对应的，知道了前者也就确定了后者，它们的信息熵是相同的。第三行的不等式是由于我们放开了 Xi 的取值条件（每个 Xi 独立取值可能会导致它们的乘积超过 n ），必然会增加结果的不确定性。而每个 Xi 的取值范围不会超出 0 到 log(n) ，最多 log(n)+1 种情况，因此 H(Xi) ≤ log(log(n)+1) ，这就得到了第四行的那个不等式。
整理上式，我们得到了 m ≥ log(n) / log(log(n)+1) ，这不但告诉我们当 n 趋于无穷大时不超过 n 的素数个数也是趋于无穷的，还给出了不超过 n 的素数个数的一个下界。
实在很酷。。我也折服了。。。谁想出来的呢
熵的世界
[...] This post was mentioned on Twitter by 阳阳猪的 GR Share, SRju690. SRju690 said: 经典证明：用信息熵证明素数无穷多 http://bit.ly/5GccMa [...]
看不懂哇，看不懂
这个太好了...和其他人share了...以后也得学学信息论...
占位
太强悍了。
内牛满面。。。。
看不懂。。
这个在Proofs from the book里面有...
没看明白，像看小说一样，看了两篇
那个PI写错了吧，应该是e吧
唉。。感觉去年信息论白学了。。
我也是，学过，但还是看不到，唉
咦，我好像在哪本书上，看到过，但看不懂
没必要引入信息熵吧，这个证明的主要思想就是集合{x|x<n,x=P1^X1 * P2^X2 * ... * Pm^Xm}的增加速度是ln(n)的多项式级别的
不用这样证明吧…… 这个看不懂……
嗯，我也认为可以不跟信息熵发生关系。证明的主要依据是集合{(x1,..xm)|0<=xi= n。
嗯，我也认为可以不跟信息熵发生关系。证明的主要依据是集合{(x1,..,xm)|0<=xi<=ln(n)｝的元素个数＞=n。
看不懂啊看不懂...
没有完全看懂
哟西，这个证明很强大！
其实我觉得证明素数无穷多还有一个简单的办法：
假设素数是有限的，那么取最大的那个n，取N=n!+1，如果N为素数，那么因为N>n，矛盾；如果N为合数，那么因为我们知道2至n之间(包括n)的所有素数都不可能整除N, 所以N的所有质因子只能>n, 也矛盾。所以问题得证。 请指正。
http://www.google.com/buzz/117275735516170172258/cewVQFK1Y53/%E5%85%B6%E5%AE%9E%E6%88%91%E8%A7%89%E5%BE%97%E8%AF%81%E6%98%8E%E7%B4%A0%E6%95%B0%E6%97%A0%E7%A9%B7%E5%A4%9A%E8%BF%98
其实我觉得证明素数无穷多还有一个简单的办法：
假设素数是有限的，那么取最大的那个n，取N=n!+1，如果N为素数，那么因为N>n，矛盾；如果N为合数，那么因为我们知道2至n之间(包括n)的所有素数都不可能整除N, 所以N的所有质因子只能>n, 也矛盾。所以问题得证。 请指正。
链接：
http://www.google.com/buzz/117275735516170172258/cewVQFK1Y53/%E5%85%B6%E5%AE%9E%E6%88%91%E8%A7%89%E5%BE%97%E8%AF%81%E6%98%8E%E7%B4%A0%E6%95%B0%E6%97%A0%E7%A9%B7%E5%A4%9A%E8%BF%98
证明素数无穷多还有一个简单的办法：
假设素数是有限的，那么取最大的那个n，取N=n!+1，如果N为素数，那么因为N>n，矛盾；如果N为合数，那么因为我们知道2至n之间(包括n)的所有素数都不可能整除N, 所以N的所有质因子只能>n, 也矛盾。所以问题得证。请指正.
[...] 用 Fermat 数和 * - 集合证明素数无穷多 素数无穷多的拓扑学证明 用信息熵证明素数无穷多 利用阶乘因子数公式证明素数无穷多 素数无穷多与两个更强的命题 [...]
是挺无穷的！