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