数论基础
本文对于数论的开头部分做一个简介。
整除
定义
设
,
。如果
,使得
,那么就说
可被
整除,记作
;
不被
整除记作
。
整除的性质:




- 设
,那么
。 - 设
,那么
。 - 设
,那么
。
约数
定义
若
,则称
是
的 倍数,
是
的 约数。
是所有非
整数的倍数。对于整数
,
的约数只有有限个。
平凡约数(平凡因数):对于整数
,
、
是
的平凡约数。当
时,
只有两个平凡约数。
对于整数
,
的其他约数称为真约数(真因数、非平凡约数、非平凡因数)。
约数的性质:
- 设整数
。当
遍历
的全体约数的时候,
也遍历
的全体约数。 - 设整数
,则当
遍历
的全体正约数的时候,
也遍历
的全体正约数。
在具体问题中,如果没有特别说明,约数总是指正约数。
带余数除法
余数
设
为两个给定的整数,
。设
是一个给定的整数。那么,一定存在唯一的一对整数
和
,满足
。
无论整数
取何值,
统称为余数。
等价于
。
一般情况下,
取
,此时等式
称为带余数除法(带余除法)。这里的余数
称为最小非负余数。
余数往往还有两种常见取法:
- 绝对最小余数:
取
的绝对值的一半的相反数。即
。 - 最小正余数:
取
。即
。
带余数除法的余数只有最小非负余数。如果没有特别说明,余数总是指最小非负余数。
余数的性质:
- 任一整数被正整数
除后,余数一定是且仅是
到
这
个数中的一个。 - 相邻的
个整数被正整数
除后,恰好取到上述
个余数。特别地,一定有且仅有一个数被
整除。
最大公约数与最小公倍数
关于公约数、公倍数、最大公约数与最小公倍数,四个名词的定义,见 最大公约数。
Warning
一些作者认为
和
的最大公约数无定义,其余作者一般将其视为
。C++ STL 的实现中采用后者,即认为
和
的最大公约数为
。
最大公约数有如下性质:
;
;- 若
,则
;
;
。进而
;- 对不全为
的整数
和非零整数
,
; - 对不全为
的整数
,若
,则
;
。
最大公约数还有如下与互素相关的性质:
- 若
且
,则
; - 若
、
且
,则
; - 若
,则
; - 若
,则
。特别地,若
,则
; - 对整数
,若
,且
,则
。
最小公倍数有如下性质:
;
;- 若
,则
; - 若
,则
;
。进而
;- 若
,则
;
;
;
。
最大公约数和最小公倍数可以组合出很多奇妙的等式,如:
;
;
。
这些性质均可通过定义或 唯一分解定理 证明,其中使用唯一分解定理的证明更容易理解。
互素
定义
若
,则称
和
互素(既约)。
若
,则称
互素(既约)。
多个整数互素,不一定两两互素。例如
、
和
互素,但是任意两个都不互素。
互素的性质与最大公约数理论:裴蜀定理(Bézout's identity)。见 裴蜀定理。
辗转相除法
辗转相除法是一种算法,也称 Euclid 算法。见 最大公约数。
素数与合数
关于素数的算法见 素数。
定义
设整数
。如果
除了平凡约数外没有其他约数,那么称
为 素数(不可约数)。
若整数
且
不是素数,则称
为 合数。
和
总是同为素数或者同为合数。如果没有特别说明,素数总是指正的素数。
整数的因数是素数,则该素数称为该整数的素因数(素约数)。
素数与合数的简单性质:
- 大于
的整数
是合数,等价于
可以表示为整数
和
(
)的乘积。 - 如果素数
有大于
的约数
,那么
。 - 大于
的整数
一定可以表示为素数的乘积。 - 对于合数
,一定存在素数
使得
。 - 素数有无穷多个。
- 所有大于
的素数都可以表示为
的形式。
算术基本定理
算术基本引理
设
是素数,
,那么
和
至少有一个成立。
算术基本引理的逆命题稍加修改也可以得到素数的另一种定义。
素数的另一种定义
对整数
,若对任意满足
的整数
均有
或
成立,则称
是素数。
Tip
这个定义的动机可以从 素理想 中找到。
算术基本定理(唯一分解定理)
设正整数
,那么必有表示:
其中
是素数。并且在不计次序的意义下,该表示唯一。
标准素因数分解式
将上述表示中,相同的素数合并,可得:
称为正整数
的标准素因数分解式。
算术基本定理和算术基本引理,两个定理是等价的。
同余
定义
设整数
。若
,称
为 模数(模),
同余于
模
,
是
对模
的 剩余。记作
。
否则,
不同余于
模
,
不是
对模
的剩余。记作
。
这样的等式,称为模
的同余式,简称 同余式。
根据整除的性质,上述同余式也等价于
。
如果没有特别说明,模数总是正整数。
式中的
是
对模
的剩余,这个概念与余数完全一致。通过限定
的范围,相应的有
对模
的最小非负剩余、绝对最小剩余、最小正剩余。
同余的性质:
- 同余是 等价关系,即同余具有
- 自反性:
。 - 对称性:若
,则
。 - 传递性:若
,则
。
- 线性运算:若
则有:
。
。
- 设
和
是两个整系数多项式,
,且
,则对任意整数
均有
。进而若
,则
。 - 若
, 则
。 - 若
,则当
成立时,有
。 - 若
,则当
成立时,有
。 - 若
,则当
成立时,有
。若
能整除
及
中的一个,则
必定能整除
中的另一个。
还有性质是乘法逆元。见 乘法逆元。
C/C++ 的整数除法和取模运算
在 C/C++ 中,整数除法和取模运算,与数学上习惯的取模和除法不一致。
对于所有标准版本的 C/C++,规定在整数除法中:
- 当除数为 0 时,行为未定义;
- 否则
(a / b) * b + a % b
的运算结果与 a
相等。
也就是说,取模运算的符号取决于除法如何取整;而除法如何取整,这是实现定义的(由编译器决定)。
从 C99和 C++11标准版本起,规定 商向零取整(舍弃小数部分);取模的符号即与被除数相同。从此以下运算结果保证为真:
| 5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;
|
同余类与剩余系
为方便讨论,对集合
和元素
,我们引入如下记号:
;
;
;
。
同余类
对非零整数
,把全体整数分成
个两两不交的集合,且同一个集合中的任意两个数模
均同余,我们把这
个集合均称为模
的 同余类 或 剩余类。用
表示含有整数
的模
的同余类。
不难证明对任意非零整数
,上述划分方案一定存在且唯一。
由同余类的定义可知:
;
;- 对任意
,要么
,要么
; - 若
,则对任意整数
均有
。
注意到同余是等价关系,所以同余类即为同余关系的等价类。
我们把模
的同余类全体构成的集合记为
,即

不难发现:
- 对任意整数
,
; - 对任意与
互质的整数
,
。
由 商群 的定义可知
,所以有时我们也会用
表示
。
由 抽屉原理 可知:
- 任取
个整数,必有两个整数模
同余。 - 存在
个两两模
不同余的整数。
由此我们给出完全剩余系的定义:
(完全)剩余系
对
个整数
,若对任意的数
,有且仅有一个数
使得
与
模
同余,则称这
个整数
为模
的 完全剩余系,简称 剩余系。
我们还可以定义模
的:
- 最小非负(完全)剩余系:
; - 最小正(完全)剩余系:
; - 绝对最小(完全)剩余系:
; - 最大非正(完全)剩余系:
; - 最大负(完全)剩余系:
。
若无特殊说明,一般我们只用最小非负剩余系。
我们注意到如下命题成立:
- 在模
的任意一个同余类中,任取两个整数
均有
。
考虑同余类
,若
,则该同余类的所有元素均与
互质,这说明我们也许可以通过类似方式得知所有与
互质的整数构成的集合的结构。
既约同余类
对同余类
,若
,则称该同余类为 既约同余类 或 既约剩余类。
我们把模
既约剩余类的个数记作
,称其为 Euler 函数。
我们把模
的既约同余类全体构成的集合记为
,即

Warning
对于任意的整数
和与
互质的整数
,
,但是
不一定为
。这一点与
不同。
由 抽屉原理 可知:
- 任取
个与
互质的整数,必有两个整数模
同余。 - 存在
个与
互质且两两模
不同余的整数。
由此我们给出既约剩余系的定义:
既约剩余系
对
个整数
,若
,且对任意满足
的数
,有且仅有一个数
使得
与
模
同余,则称这
个整数
为模
的 既约剩余系、缩剩余系 或 简化剩余系。
类似地,我们也可以定义最小非负既约剩余系等概念。
若无特殊说明,一般我们只用最小非负既约剩余系。
剩余系的复合
对正整数
,我们有如下定理:
若
,令
分别为模
的 完全 剩余系,则对任意与
互质的
均有:
为模
的 完全 剩余系。进而,若
,令
分别为模
的 完全 剩余系,则:
为模
的 完全 剩余系。
证明
只需证明对任意满足
的
,
,都有:
实际上,由
,我们有
,进而
,由
可知
,进而有
。
进一步,
,则
,即
。
因此,

Tip
该定理等价于证明 Euler 函数为 积性函数。
证明
令
分别为模
的完全剩余系,我们已经证明了
为模
的完全剩余系。令
,显然
为模
的既约剩余系,所以我们只需证明
即可。
显然
。
任取
,其中
且
,有
,由
可得
因此可得
且
,即
。
任取
,其中
且
,有
且
,由
可得
因此可得
,即
。
综上所述,
为模
的 既约 剩余系。
数论函数
数论函数(也称算数函数)指定义域为正整数的函数。数论函数也可以视作一个数列。
积性函数
定义
在数论中,若函数
满足
,且
对任意互质的
都成立,则
为 积性函数。
在数论中,若函数
满足
且
对任意的
都成立,则
为 完全积性函数。
性质
若
和
均为积性函数,则以下函数也为积性函数:

对正整数
,设其唯一质因数分解为
,其中
为质数。
若
为积性函数,则有
。
若
为完全积性函数,则有
。
例子
- 单位函数:
。(完全积性) - 恒等函数:
,
通常简记作
。(完全积性) - 常数函数:
。(完全积性) - 除数函数:
。
通常简记作
或
,
通常简记作
。 - 欧拉函数:
。 - 莫比乌斯函数:
,其中
表示
的本质不同质因子个数。
加性函数
定义
在数论中,若函数
满足
且
对任意互质的
都成立,则
为 加性函数。
在数论中,若函数
满足
且
对任意的
都成立,则
为 完全加性函数。
加性函数
本节中的加性函数指数论上的加性函数 (Additive function),应与代数中的 Additive map 做区分。
性质
对正整数
,设其唯一质因数分解为
,其中
为质数。
若
为加性函数,则有
。
若
为完全加性函数,则有
。
例子
为方便叙述,令所有质数组成的集合为
.
- 所有质因子数目:
。(完全加性) - 相异质因子数目:
。 - 所有质因子之和:
。(完全加性) - 相异质因子之和:
。
参考资料与注释
- 潘承洞,潘承彪。初等数论。北京大学出版社。
本页面最近更新:2025/5/21 14:28:09,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:383494, buuzzing, c-forrest, cr4c1an, Emp7iness, Enter-tainer, Great-designer, jifbt, Kaiser-Yang, Koishilll, ksyx, Marcythm, oosquare, Qiu-Quanzhi, Saisyc, sshwy, Tiphereth-A, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用