跳转至

数论基础

本文对于数论的开头部分做一个简介。

整除

定义

。如果 ,使得 ,那么就说 可被 整除,记作 不被 整除记作

整除的性质:

  • ,那么
  • ,那么
  • ,那么

约数

定义

,则称 倍数约数

是所有非 整数的倍数。对于整数 的约数只有有限个。

平凡约数(平凡因数):对于整数 的平凡约数。当 时, 只有两个平凡约数。

对于整数 的其他约数称为真约数(真因数、非平凡约数、非平凡因数)。

约数的性质:

  • 设整数 。当 遍历 的全体约数的时候, 也遍历 的全体约数。
  • 设整数 ,则当 遍历 的全体正约数的时候, 也遍历 的全体正约数。

在具体问题中,如果没有特别说明,约数总是指正约数。

带余数除法

余数

为两个给定的整数,。设 是一个给定的整数。那么,一定存在唯一的一对整数 ,满足

无论整数 取何值, 统称为余数。 等价于

一般情况下,,此时等式 称为带余数除法(带余除法)。这里的余数 称为最小非负余数。

余数往往还有两种常见取法:

  • 绝对最小余数: 的绝对值的一半的相反数。即
  • 最小正余数:。即

带余数除法的余数只有最小非负余数。如果没有特别说明,余数总是指最小非负余数。

余数的性质:

  • 任一整数被正整数 除后,余数一定是且仅是 个数中的一个。
  • 相邻的 个整数被正整数 除后,恰好取到上述 个余数。特别地,一定有且仅有一个数被 整除。

最大公约数与最小公倍数

关于公约数、公倍数、最大公约数与最小公倍数,四个名词的定义,见 最大公约数

Warning

一些作者认为 的最大公约数无定义,其余作者一般将其视为 。C++ STL 的实现中采用后者,即认为 的最大公约数为 4

最大公约数有如下性质:

  • ,则
  • 。进而
  • 对不全为 的整数 和非零整数
  • 对不全为 的整数 ,若 ,则

最大公约数还有如下与互素相关的性质:

  • ,则
  • ,则
  • ,则
  • ,则 。特别地,若 ,则
  • 对整数 ,若 ,且 ,则

最小公倍数有如下性质:

  • ,则
  • ,则
  • 。进而
  • ,则

最大公约数和最小公倍数可以组合出很多奇妙的等式,如:

这些性质均可通过定义或 唯一分解定理 证明,其中使用唯一分解定理的证明更容易理解。

互素

定义

,则称 互素既约)。

,则称 互素既约)。

多个整数互素,不一定两两互素。例如 互素,但是任意两个都不互素。

互素的性质与最大公约数理论:裴蜀定理(Bézout's identity)。见 裴蜀定理

辗转相除法

辗转相除法是一种算法,也称 Euclid 算法。见 最大公约数

素数与合数

关于素数的算法见 素数

定义

设整数 。如果 除了平凡约数外没有其他约数,那么称 素数不可约数)。

若整数 不是素数,则称 合数

总是同为素数或者同为合数。如果没有特别说明,素数总是指正的素数。

整数的因数是素数,则该素数称为该整数的素因数(素约数)。

素数与合数的简单性质:

  • 大于 的整数 是合数,等价于 可以表示为整数 )的乘积。
  • 如果素数 有大于 的约数 ,那么
  • 大于 的整数 一定可以表示为素数的乘积。
  • 对于合数 ,一定存在素数 使得
  • 素数有无穷多个。
  • 所有大于 的素数都可以表示为 的形式1

算术基本定理

算术基本引理

是素数,,那么 至少有一个成立。

算术基本引理是素数的本质属性,也是素数的真正定义。

算术基本定理(唯一分解定理)

设正整数 ,那么必有表示:

其中 是素数。并且在不计次序的意义下,该表示唯一。

标准素因数分解式

将上述表示中,相同的素数合并,可得:

称为正整数 的标准素因数分解式。

算术基本定理和算术基本引理,两个定理是等价的。

同余

定义

设整数 。若 ,称 模数), 同余于 对模 剩余。记作

否则, 不同余于 不是 对模 的剩余。记作

这样的等式,称为模 的同余式,简称 同余式

根据整除的性质,上述同余式也等价于

如果没有特别说明,模数总是正整数。

式中的 对模 的剩余,这个概念与余数完全一致。通过限定 的范围,相应的有 对模 的最小非负剩余、绝对最小剩余、最小正剩余。

同余的性质:

  • 同余是 等价关系,即同余具有
    • 自反性:
    • 对称性:若 ,则
    • 传递性:若 ,则
  • 线性运算:若 则有:
  • 是两个整系数多项式,,且 ,则对任意整数 均有 。进而若 ,则
  • , 则
  • ,则当 成立时,有
  • ,则当 成立时,有
  • ,则当 成立时,有 。若 能整除 中的一个,则 必定能整除 中的另一个。

还有性质是乘法逆元。见 乘法逆元

C/C++ 的整数除法和取模运算

在 C/C++ 中,整数除法和取模运算,与数学上习惯的取模和除法不一致。

对于所有标准版本的 C/C++,规定在整数除法中:

  1. 当除数为 0 时,行为未定义;
  2. 否则 (a / b) * b + a % b 的运算结果与 a 相等。

也就是说,取模运算的符号取决于除法如何取整;而除法如何取整,这是实现定义的(由编译器决定)。

从 C992和 C++113标准版本起,规定 商向零取整(舍弃小数部分);取模的符号即与被除数相同。从此以下运算结果保证为真:

1
2
3
4
5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;

同余类与剩余系

为方便讨论,对集合 和元素 ,我们引入如下记号:

同余类

对非零整数 ,把全体整数分成 个两两不交的集合,且同一个集合中的任意两个数模 均同余,我们把这 个集合均称为模 同余类剩余类。用 表示含有整数 的模 的同余类。

不难证明对任意非零整数 ,上述划分方案一定存在且唯一。

由同余类的定义可知:

  • 对任意 ,要么 ,要么
  • ,则对任意整数 均有

注意到同余是等价关系,所以同余类即为同余关系的等价类。

我们把模 的同余类全体构成的集合记为 ,即

不难发现:

  • 对任意整数
  • 对任意与 互质的整数

商群 的定义可知 ,所以有时我们也会用 表示

抽屉原理 可知:

  • 任取 个整数,必有两个整数模 同余。
  • 存在 个两两模 不同余的整数。

由此我们给出完全剩余系的定义:

(完全)剩余系

个整数 ,若对任意的数 ,有且仅有一个数 使得 同余,则称这 个整数 为模 完全剩余系,简称 剩余系

我们还可以定义模 的:

  • 最小非负(完全)剩余系:
  • 最小正(完全)剩余系:
  • 绝对最小(完全)剩余系:
  • 最大非正(完全)剩余系:
  • 最大负(完全)剩余系:

若无特殊说明,一般我们只用最小非负剩余系。


我们注意到如下命题成立:

  • 在模 的任意一个同余类中,任取两个整数 均有

考虑同余类 ,若 ,则该同余类的所有元素均与 互质,这说明我们也许可以通过类似方式得知所有与 互质的整数构成的集合的结构。

既约同余类

对同余类 ,若 ,则称该同余类为 既约同余类既约剩余类

我们把模 既约剩余类的个数记作 ,称其为 Euler 函数

我们把模 的既约同余类全体构成的集合记为 ,即

Warning

对于任意的整数 和与 互质的整数 ,但是 不一定为 。这一点与 不同。

抽屉原理 可知:

  • 任取 个与 互质的整数,必有两个整数模 同余。
  • 存在 个与 互质且两两模 不同余的整数。

由此我们给出既约剩余系的定义:

既约剩余系

个整数 ,若 ,且对任意满足 的数 ,有且仅有一个数 使得 同余,则称这 个整数 为模 既约剩余系缩剩余系简化剩余系

类似地,我们也可以定义最小非负既约剩余系等概念。

若无特殊说明,一般我们只用最小非负既约剩余系。

剩余系的复合

对正整数 ,我们有如下定理:

  • ,令 分别为模 完全 剩余系,则对任意与 互质的 均有:

    为模 完全 剩余系。进而,若 ,令 分别为模 完全 剩余系,则:

    为模 完全 剩余系。

证明

只需证明对任意满足 ,都有:

实际上,由 ,我们有 ,进而 ,由 可知 ,进而有

进一步,,则 ,即

因此,

  • ,令 分别为模 既约 剩余系,则:

    为模 既约 剩余系。

Tip

该定理等价于证明 Euler 函数为 积性函数

证明

分别为模 的完全剩余系,我们已经证明了

为模 的完全剩余系。令 ,显然 为模 的既约剩余系,所以我们只需证明 即可。

显然

任取 ,其中 ,有 ,由 可得

因此可得 ,即

任取 ,其中 ,有 ,由 可得

因此可得 ,即

综上所述,

为模 既约 剩余系。

数论函数

数论函数(也称算数函数)指定义域为正整数的函数。数论函数也可以视作一个数列。

积性函数

定义

在数论中,若函数 满足 ,且 对任意互质的 都成立,则 积性函数

在数论中,若函数 满足 对任意的 都成立,则 完全积性函数

性质

均为积性函数,则以下函数也为积性函数:

对正整数 ,设其唯一质因数分解为 ,其中 为质数。

为积性函数,则有

为完全积性函数,则有

例子

  • 单位函数:。(完全积性)
  • 恒等函数: 通常简记作 。(完全积性)
  • 常数函数:。(完全积性)
  • 除数函数: 通常简记作 通常简记作
  • 欧拉函数:
  • 莫比乌斯函数:,其中 表示 的本质不同质因子个数。

加性函数

定义

在数论中,若函数 满足 对任意互质的 都成立,则 加性函数

在数论中,若函数 满足 对任意的 都成立,则 完全加性函数

加性函数

本节中的加性函数指数论上的加性函数 (Additive function),应与代数中的 Additive map 做区分。

性质

对正整数 ,设其唯一质因数分解为 ,其中 为质数。

为加性函数,则有

为完全加性函数,则有

例子

为方便叙述,令所有质数组成的集合为 .

  • 所有质因子数目:。(完全加性)
  • 相异质因子数目:
  • 所有质因子之和:。(完全加性)
  • 相异质因子之和:

参考资料与注释

  1. 潘承洞,潘承彪。初等数论。北京大学出版社。