您当前的位置:首页 > 学习 > 阅览室

利用阶乘因子数公式证明素数无穷多

时间:12-10来源:作者:点击数:

搞过 OI/ACM 的同学们想必对一道经典题目印象极深:求 n 的阶乘末尾有多少个 0 。注意到末尾的一个 0 是由一个因子 2 和一个因子 5 相乘产生的;但在 n 的阶乘里,因子 5 的个数通常远远少于因子 2 。因此这个问题就等价于问 n 的阶乘里有多少个因子 5 。在 n 的阶乘式中,每个 5 的倍数里都含有一个因子 5 ,每个 25 的倍数里都还含有另外一个因子 5 ,每个 125 的倍数里都还有第三个因子 5 ……因此, n 的阶乘里因子 5 的个数的计算公式就是 ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … 。如果把 K 的阶乘里素因子 p 的个数记作 Φ(p, K) ,则 Φ(p, K) = Σ⌊K/(p^i)⌋ 。有意思的是,最近 The American Mathematical Monthly 上的一篇文章利用这个公式瞬间证明了素数无穷多的定理。

如果素数是有限的,则 K 的阶乘就可以写成所有 p^Φ(p, K) 的乘积,其中的 p 取遍所有的素数。注意到 Φ(p, K) = Σ⌊K/(p^i)⌋ < Σ(K/(p^i)) = K/(p-1) < K ,因此对任意正整数 K 都有 K! < (Πp)^K ,其中 Πp 表示所有素数的乘积。但当 K 充分大的时候, K! 显然会超过一个常数的 K 次方,矛盾。因此素数不可能是有限的。 来源:http://www.cut-the-knot.org/wiki-math(http://www.cut-the-knot.org/wiki-math/index.php?n=Arithmetic.InfinitudeOfPrimesFromLegendresFormula)

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门
本栏推荐