具体数学-第10课（素数和阶乘的有趣性质）
原文链接：
具体数学-第10课 - WeiYang Bloggodweiyang.com
欧几里得数
首先我们来证明一下，素数有无穷多个。
假设素数只有
个，分别为
，那么我们构造下面的数字：
显然
无法被
中的任意一个整除，那么要么
可以被其他的素数整除，要么
自己就是一个素数。所以素数有无穷多个。
下面我们来定义欧几里得数，是用递归形式来定义的：
那么欧几里得数是否是素数呢？当然不是的，
。
但是欧几里得数还是有很多奇妙的性质。
性质1
证明： 假设
，那么有
性质2 如果令
等于
的最小素因子，那么
就是一个不重复的素数序列，这也证明了素数有无穷多个。 性质3
在后面的章节可以证明：
其中
下面我们稍稍探究一下下面这个数的性质：
这个数如果是素数，那么就被叫做梅森素数，那么它在什么情况下是素数呢？
首先
不能是合数，因为有
但是如果
是素数，这个数也不一定是素数，2017年年末美国一个电气工程师发现了人类历史上最大的梅森素数——
。
阶乘
阶乘定义如下：
所以有
由基本不等式可以得到
所以
所以
这里得到了阶乘的一个粗略范围，在后面章节中，我们会得到阶乘的一个更精确的表达式：
这就是斯特林数，搞ACM还是很有用的。
下面我们来探讨
中含有多少个素因子
，个数记为
。
从特殊情况讨论起，当
的时候，我们首先看
含有多少个2，然后看有多少个4，再看有多少个8，依次下去，所以答案为：
可以看出，这个答案不就是
的二进制表示不停右移1位，然后相加吗？所以又可以写成：
其中
表示
的二进制表示中1的个数。
推广到一般情况：
放缩一下有：
如果我们令
和
可以发现：
但是这个式子在什么情况下相等呢？这仍然是一个未解之谜。
所以
对
的贡献度满足如下式子：
又因为
，所以
假设素数只有
个，分别为
，那么有
如果我们令
，那么
这与我们之前推过的不等式矛盾！所以一定有无穷个素数。
设小于等于
的素数个数为
，所以
根据斯特林数公式，我们可以得到
互素
定义
和
互素定义为
，记作
。
互素也有很多性质。
性质1
性质2
其中
就是两个数的素数指数表示法，详细定义见上一节课。 或者可以表示为
性质3
Stern-Brocot树
如上图所示，Stern-Brocot树就是0到1之间的分数生成的一棵二叉树。
初始时只有
两个数，第一轮将两者分母相加，分子也相加作为新的分数的分母分子。第二轮再对相邻的两个分数做相同的操作，生成新的分数序列。不断生成下去，得到了上图的二叉树。
Stern-Brocot树有下面四个性质：
- 0到1之间的所有有理数都出现在了这棵树中。
- 每个分数仅出现了1次。
- 每个分数都是不可约分的，即分子分母互素。
- 生成的序列是单调递增的。
下面我们来一个一个证明。
引理 对于相邻的两个分数
，满足：
证明 用数学归纳法证明。
性质4就是证明：
结论是很显然的，这样性质2同时就成立了。
性质1的话，对于任意有理数
，假设
。 我们采用如下策略生成
。
- 如果
，那么成功。
- 如果
，那么令
。
- 如果
，那么令
。
那么有
所以
而左边式子就等于
，所以
因为
都在不断增加，所以最多
轮就能生成
。
性质3的话，同样用数学归纳法。通过引理可以得到
由扩展欧几里得定理可以得到
与
互素。
Farey序列 我们引申出Farey序列的概念，定义如下：
关于它的更多性质，留到下一节课继续。