[具体数学]第四章·数论

第四章·数论分9节，从最基础的整除一直讲到了莫比乌斯函数和欧拉函数

注意：过于基础的数论知识就略去了

整除性

定义

整除定义略去。

$gcd(m,n)$ 和 $\text{lcm}(m,n)$ 的定义略去，注意它们有关系式： $$gcd(m,n)\cdot \text{lcm}(m,n)=mn$$ 考虑 $m,n$ 的质因数分解即可证。

欧几里得算法

欧几里得算法（辗转相除法） 解 $gcd$，基于定理： $$gcd(m,n)=gcd(nmodm,m),m>0$$ 证：设 $d$ 是 $m,n$ 的一个公因数，$n=ad,m=bd$，则 $nmodm=n-m\lfloor n/m\rfloor =ad-bd\lfloor a/b\rfloor$ 也是 $d$ 的倍数。这说明任意 $m,n$ 的公因数都是 $nmodm,m$ 的公因数，$gcd$ 自然不例外。$◻$

可以从上述的证明过程中提出来一个定理： $$k\mid m\mathrm{且}k\mid n⟺k\mid gcd(m,n)$$

由欧几里得算法可以得到扩展欧几里得算法，用于解不定方程。（竞赛基础，略去）

常用的和式变换

在之后的数论推导中，我们经常遇到带有整除的和式，为此，需要熟悉几个常用的和式变换。

变换1： $$ 很简单。

变换2： $$ 相当于一次变量替换 $$.

变换3： $$ 和式换序+变量替换 $$.

素数

算术基本定理

算术基本定理（唯一分解定理）：每一个正整数都能用唯一的方式写成： $$ 这玩意儿看起来很显然，但是我们仍然需要证明。

证：归纳法。$$ 显然；现在研究 $$ 的情况。设小于 $$ 的数都满足该定理，假设 $$，其中 $$ 且 $$，我们只需要证明 $$ 且 $$。取第一个使得 $$ 的 $$，不妨假设 $$，那么根据贝祖定理，存在整数 $$ 使得 $$，于是 $$。由于 $$ 整除左式，所以 $$ 整除右式，即 $$。但是 $$ 比 $$ 都小且 $$ 都是质数，所以矛盾，假设不成立，$$。用 $$ 除分解式两边，得到 $$，由归纳假设，这些数对应相等。 $$

为什么说这么显然的东西需要证明呢？因为我们稍微扩展一下“质数”的定义，它就不对了。

考虑集合 $$。如果 $$，称 $$ 是单位，因为它具有逆元（$$）。称 $$ 中不能写成两个非单位数乘积的非单位数为素元。可以证明，$$ 都是 $$ 中的素元，于是 $$ 被分解成了两种表示，不是唯一分解。

欧几里得数

欧几里得提出过一个素数无穷性的著名证明：

假设只有有限个素数，设为 $$，那么考虑数 $$，它不被任何这 $$ 个素数整除，于是 $$ 被另一个素数整除或者本身就是素数，均与假设矛盾，故素数无穷。$$

据此，我们可以用递归式定义出欧几里得数 $$（也称 $$）： $$ 所有的欧几里得数都是互质的，但是不都是质数。

我们试着解出它的封闭形式： $$ 可以证明：存在一个常数 $$，使得 $$

梅森数

形如 $$（$$ 为素数）的数称为梅森数 $$。

注意 $$，当 $$ 为合数时必不是质数，因为 $$；但 $$ 为质数时 $$ 不一定是质数。

素数定理

$$

或 $$

孪生素数

$$ 和 $$ 均是素数，称它们为孪生素数。至今仍未证明出有无穷多对孪生素数。

阶乘的因子

考虑阶乘 $$，记 $$ 表示能整除 $$ 的素数 $$ 的最大幂（例如，$$，因为 $$ 而 $$）

考虑 $$ 中的数，如果它能被 $$ 整除，它给答案的贡献为 $$；如果它能被 $$ 整除，它给答案的贡献在 $$ 的基础上再 $$；……而 $$ 中能被 $$ 整除的数有 $$ 个，所以我们有公式： $$ 我们可以做一个简单的放缩，得到 $$ 的一个上界： $$ 而事实上，这个放缩已经很好了。

该上界可以反过来得到 $$ 的上界，注意这个式子表示的是 $$ 对 $$ 的贡献： $$ 我们再做一步很大的放缩 $$： $$ 也就是说，任何一个素数 $$ 对 $$ 的贡献都小于 $$. 用这个结论，我们可以给出一个素数无穷的证明方法：

假设只有 $$ 个素数 $$，由于每一个素数对 $$ 的贡献 $$，故 $$. 但是该式对足够大的 $$ 显然不成立（阶乘增长比指数要快），故假设不成立。$$

互素

符号

$$

也可以是 $$. （$$ 在无歧义时指代 $$）

重要法则： $$

$$ 树和 $$ 级数

从两个分数：$$ 出发，不断重复操作：在两个相邻的分数 $$ 之间插入它们的中位分数 $$.

上述操作过程可以形成一棵树：

基本性质：如果 $$ 和 $$ 是这个构造中任何一个阶段的相邻分数，那么有： $$ 证：归纳法。首先对于 $$ 时正确的；其次，插入 $$ 时，有： $$ $$

性质：

• 出现在 $$ 树中的分数都是最简分数。

  证：设 $$ 出现在树中，$$ 是 $$ 的任何一个公因子，那么 $$。由基本性质可知：$$，于是 $$，因此 $$. $$

• 所有的最简分数都会在 $$ 树中出现。

  证：对于最简分数 $$，假设我们在某阶段有：$$，若 $$，则找到了 $$；若 $$，则在 $$ 和 $$ 中继续寻找；若 $$，则在 $$ 和 $$ 中继续寻找。这个过程必定有限，因为我们有： $$ 而 $$ 始终在增加，故最多 $$ 步就能找到 $$.

阶为 $$ 的法里级数 $$ 记为 $$，表示介于 $$ 和 $$ 之间的，分母不超过 $$ 的所有最简分数组成的集合，按递增的次序排列。例如：$$.

$$ 的构造和之前类似，从 $$ 出发，不断插入中位分数，不过不插入分母大于 $$ 的数。换句话说，$$ 定义了 $$ 树的一颗子树，去除了分母 $$ 的分支。于是，$$ 级数也满足性质：设 $$ 和 $$ 是其中的相邻元素，则 $$.

我们可以把 $$ 树看成一个表示有理数的数系，因为每一个有理数都在其中恰好出现一次。用 $$ 表示从树根往下走的方式，这样每一个有理数都可以唯一地被一个 $$ 构成的字符串表示，例如 $$ 可以表示为 $$. 特别地，$$ 由空串表示，记为 $$.

现在有两个问题：给定一个最简分数，它的字符串表示是什么？给定一个字符串，它表示的最简分数是什么？

编程的话，我们直接按照规则在 $$ 树上往左或者往右走即可。但是如果要在数学上很好地表达出来，我们可以这样考虑：

设 $$ 表示 $$ 对应的最简分数，$$ 是树的上一层中 $$ 前后的树，则 $$. 考虑矩阵： $$ 向左走一步时，$$ 要变成 $$，需要右乘 $$；向右走一步时，$$ 要变成 $$，需要右乘 $$. 也就是说：定义 $$ 则： $$ 结合初始条件 $$，容易归纳得到： $$ 例如，$$，说明 $$ 对应 $$ 和 $$ 的中位分数 $$.

另外，如果我们给定的是一个无理数，我们会在树上无限地走下去，并不断更新所给无理数的上下界，这么做可以让我们去近似一个无理数。

欧几里得算法和有理数的 $$ 表示之间有密切的联系。给定 $$，我们得到 $$ 个 $$，然后得到 $$ 个 $$，然后得到 $$ 个 $$……这些数正好是欧几里得算法中出现的数。

$$：同余关系

定义略。

同余是一个等价关系，满足自反律、对称律、传递律。

满足加、减、乘、幂。

除法：

• $$ 时，满足消去律：$$.

• 一般的，有： $$

定理： $$ 定理： $$ 当 $$ 时，有上述定理的特殊情况： $$

独立剩余

一个整数 $$ 表示成为关于一组互素的模的剩余序列： $$ 注意独立性：以 $$ 为例，$$，$$，那么 $$. 对每个 $$ 分别做运算即可。

如果知道了一个给定的剩余序列，如何反过来求出 $$？中国剩余定理。

上述理论的一个小应用：$$ 在模 $$ 下有多少个解？

• 先考虑 $$ 的情形：

  当 $$ 时，这是二次探测定理： $$ 仅有两解：$$.

  当 $$ 时，$$，由于 $$ 和 $$ 中有一个数能被 $$ 整除但不能被 $$ 整除，所以另一个必定能被 $$ 整除。因此，当 $$ 时有 $$ 解：$$.

• 考虑 $$，由于素数之间相互独立，我们只需要把每个素数的解的数量乘起来即可。对 $$ 都是两解，对 $$ 需要进行一些修正，如果非要写成一个式子，那就是： $$

几个定理

费马小定理

若 $$ 是质数，则： $$ 特别地，若 $$ 不是 $$ 的倍数，则： $$ Proof：设 $$ 为质数，$$ 不是 $$ 的倍数（即 $$）。取一模 $$ 的完全剩余系 $$，容易证明 $$ 也是模 $$ 的完全剩余系。于是有： $$ $$

欧拉定理

若 $$，则： $$ Proof：取一模 $$ 的缩剩余系 $$，容易证明 $$ 也是模 $$ 的一个缩剩余系。于是有： $$ $$

威尔逊定理

$$ 为质数的充要条件是： $$ Proof：

充分性：$$。设 $$，则 $$；又 $$，而 $$，故只能是 $$，所以 $$ 是质数；

必要性： 只需证：$$。当 $$ 时，成立；当 $$ 时，$$ 是奇数，现在证明：$$ 这偶数个数字可以两两配对，使得每一对都互为模 $$ 意义下的逆元。首先，对于 $$，一定能找到 $$ 使得 $$ 互为逆元；其次，对于 $$，$$ 不可能是自己的逆元；再次，假设 $$ 互为逆元，则必不会有第三者 $$ 与 $$ 或 $$ 为逆元，综上易知，$$ 可以两两配对形成逆元对。于是，$$ 成立。

$$

$$ 函数与 $$ 函数

欧拉函数

$$ 表示 $$ 中与 $$ 互质的数的个数，即：$$.

totient 这个单词是一个喜欢发明新词汇的英国数学家 $$ 发明的。

• 对于素数 $$，显然 $$

• 对于素数幂 $$，所有与 $$ 互质的数 $$ 满足：$$，而在 $$ 中 $$ 的倍数有 $$ 个，所以 $$ 就是总数减掉这些倍数： $$

• 对于非素数幂 $$，可以写作：$$，其中 $$。如果 $$，那么 $$，于是 $$（由 $$ 可知）。于是乎，$$ 有 $$ 种选法，$$ 有 $$ 种选法，根据中国剩余定理，给定一个 $$ 和 $$ 就能唯一确定下 $$，所以一共就有 $$ 种 $$ 的选法，也就是说： $$

积性函数：如果 $$，并且 $$ 那么称正整数的函数 $$ 是积性的（multiplicable）。从刚才的叙述中可以知道，欧拉函数 $$ 是积性的。

从定义可以看出，积性函数的值完全由它在素数幂的值所决定。若把 $$ 质因子分解：$$，那么根据积性有： $$

把欧拉函数套入公式，得到： $$ 考虑以 $$ 为分母的所有真分数：$$，把它们化简约分之后可以按照分母分类，它们的分母全是 $$ 的约数，而以 $$ 为分母的所有分数恰有 $$ 个。于是乎，我们得到了如下公式： $$

上面一段话不太“数学”，用“更数学”的话来说是：设 $$ 表示小于等于 $$ 的数中与 $$ 的 $$ 为 $$ 的数的个数，即 $$. 那么显然有：$$. 又因为 $$，所以 $$，于是 $$. $$

用 $$ 卷积可以写成： $$

如果 $$ 和 $$ 满足：$$，那么知道 $$ 和 $$ 其中一个是积性的，就可以推出另一个也是积性的。

更一般地，设 $$，那么 $$ 三者的积性知二推一。

莫比乌斯函数

莫比乌斯函数 $$ 由下式定义： $$

用 $$ 卷积的形式写作： $$

由于 $$ 显然积性，所以 $$ 是积性函数。又根据定义可知 $$，于是套用积性函数的公式可得： $$ $$ 和 $$ 在1857年注意到了“反演原理”： $$

用 $$ 卷积的形式写作： $$ 注意到 $$，即 $$ 是 $$ 的逆元，推导也就简单了。

如果对我们之前得到的公式 $$ 进行莫比乌斯反演，就可以得到： $$

用 $$ 卷积的形式写作： $$ 我们可以把它与欧拉函数的决定式 $$ 之间建立起关系：注意到 $$ 中 $$ 常常取 $$，事实上，仅有 $$ 项不是 $$. 把 $$ 展开来得到的 $$ 项，正好与之对应。

欧拉函数前缀和

定义： $$ 为欧拉函数的前缀和函数。注意这里 $$，所以 $$.

我们有恒等式： $$ 证：对于所有满足 $$ 的分数 $$，如果我们既计入最简分数，也计入未化简的分数，那么一共有 $$ 种；换一个角度，考虑分子分母公因数为 $$ 的所有分数个数，相当于 $$ 的所有最简分数个数，即 $$. 枚举 $$ 得到左式 $$. $$

这个恒等式可以看成隐含的 $$ 的递归式，不过为了更方便计算，我们引入莫比乌斯反演： $$

事实上，莫比乌斯是因为这个反演原理而非之前叙述的那个而创造的莫比乌斯函数。

证：

必要性： $$ 充分性： $$ $$

运用上述莫比乌斯反演，我们反解出 $$： $$

在这里你可以发现，欧拉函数前缀和可以 $$ 地求出，比杜教筛优秀（但是依赖于莫比乌斯函数前缀和，所以还是得杜教筛）