数论基础
本文对于数论的开头部分做一个简介。
整除
定义
设
整除的性质:
- 设
,那么 。 - 设
,那么 。 - 设
,那么 。
约数
定义
若
平凡约数(平凡因数):对于整数
对于整数
约数的性质:
- 设整数
。当 遍历 的全体约数的时候, 也遍历 的全体约数。 - 设整数
,则当 遍历 的全体正约数的时候, 也遍历 的全体正约数。
在具体问题中,如果没有特别说明,约数总是指正约数。
带余数除法
余数
设
无论整数
一般情况下,
余数往往还有两种常见取法:
- 绝对最小余数:
取 的绝对值的一半的相反数。即 。 - 最小正余数:
取 。即 。
带余数除法的余数只有最小非负余数。如果没有特别说明,余数总是指最小非负余数。
余数的性质:
- 任一整数被正整数
除后,余数一定是且仅是 到 这 个数中的一个。 - 相邻的
个整数被正整数 除后,恰好取到上述 个余数。特别地,一定有且仅有一个数被 整除。
最大公约数与最小公倍数
关于公约数、公倍数、最大公约数与最小公倍数,四个名词的定义,见 最大公约数。
Warning
一些作者认为
最大公约数有如下性质:
; ;- 若
,则 ; ; 。进而 ;- 对不全为
的整数 和非零整数 , ; - 对不全为
的整数 ,若 ,则 ; 。
最大公约数还有如下与互素相关的性质:
- 若
且 ,则 ; - 若
、 且 ,则 ; - 若
,则 ; - 若
,则 。特别地,若 ,则 ; - 对整数
,若 ,且 ,则 。
最小公倍数有如下性质:
; ;- 若
,则 ; - 若
,则 ; 。进而 ;- 若
,则 ; ; ; 。
最大公约数和最小公倍数可以组合出很多奇妙的等式,如:
; ; 。
这些性质均可通过定义或 唯一分解定理 证明,其中使用唯一分解定理的证明更容易理解。
互素
定义
若
若
多个整数互素,不一定两两互素。例如
互素的性质与最大公约数理论:裴蜀定理(Bézout's identity)。见 裴蜀定理。
辗转相除法
辗转相除法是一种算法,也称 Euclid 算法。见 最大公约数。
素数与合数
关于素数的算法见 素数。
定义
设整数
若整数
整数的因数是素数,则该素数称为该整数的素因数(素约数)。
素数与合数的简单性质:
- 大于
的整数 是合数,等价于 可以表示为整数 和 ( )的乘积。 - 如果素数
有大于 的约数 ,那么 。 - 大于
的整数 一定可以表示为素数的乘积。 - 对于合数
,一定存在素数 使得 。 - 素数有无穷多个。
- 所有大于
的素数都可以表示为 的形式1。
算术基本定理
算术基本引理
设
算术基本引理是素数的本质属性,也是素数的真正定义。
算术基本定理(唯一分解定理)
设正整数
其中
标准素因数分解式
将上述表示中,相同的素数合并,可得:
称为正整数
算术基本定理和算术基本引理,两个定理是等价的。
同余
定义
设整数
否则,
这样的等式,称为模
根据整除的性质,上述同余式也等价于
如果没有特别说明,模数总是正整数。
式中的
同余的性质:
- 同余是 等价关系,即同余具有
- 自反性:
。 - 对称性:若
,则 。 - 传递性:若
,则 。
- 自反性:
- 线性运算:若
则有: 。 。
- 设
和 是两个整系数多项式, ,且 ,则对任意整数 均有 。进而若 ,则 。 - 若
, 则 。 - 若
,则当 成立时,有 。 - 若
,则当 成立时,有 。 - 若
,则当 成立时,有 。若 能整除 及 中的一个,则 必定能整除 中的另一个。
还有性质是乘法逆元。见 乘法逆元。
C/C++ 的整数除法和取模运算
在 C/C++ 中,整数除法和取模运算,与数学上习惯的取模和除法不一致。
对于所有标准版本的 C/C++,规定在整数除法中:
- 当除数为 0 时,行为未定义;
- 否则
(a / b) * b + a % b
的运算结果与a
相等。
也就是说,取模运算的符号取决于除法如何取整;而除法如何取整,这是实现定义的(由编译器决定)。
从 C992和 C++113标准版本起,规定 商向零取整(舍弃小数部分);取模的符号即与被除数相同。从此以下运算结果保证为真:
1 2 3 4 |
|
同余类与剩余系
为方便讨论,对集合
; ; ; 。
同余类
对非零整数
不难证明对任意非零整数
由同余类的定义可知:
; ;- 对任意
,要么 ,要么 ; - 若
,则对任意整数 均有 。
注意到同余是等价关系,所以同余类即为同余关系的等价类。
我们把模
不难发现:
- 对任意整数
, ; - 对任意与
互质的整数 , 。
由 商群 的定义可知
由 抽屉原理 可知:
- 任取
个整数,必有两个整数模 同余。 - 存在
个两两模 不同余的整数。
由此我们给出完全剩余系的定义:
(完全)剩余系
对
我们还可以定义模
- 最小非负(完全)剩余系:
; - 最小正(完全)剩余系:
; - 绝对最小(完全)剩余系:
; - 最大非正(完全)剩余系:
; - 最大负(完全)剩余系:
。
若无特殊说明,一般我们只用最小非负剩余系。
我们注意到如下命题成立:
- 在模
的任意一个同余类中,任取两个整数 均有 。
考虑同余类
我们把模
Warning
对于任意的整数
由 抽屉原理 可知:
- 任取
个与 互质的整数,必有两个整数模 同余。 - 存在
个与 互质且两两模 不同余的整数。
由此我们给出既约剩余系的定义:
既约剩余系
对
类似地,我们也可以定义最小非负既约剩余系等概念。
若无特殊说明,一般我们只用最小非负既约剩余系。
剩余系的复合
对正整数
若
,令 分别为模 的 完全 剩余系,则对任意与 互质的 均有:为模
的 完全 剩余系。进而,若 ,令 分别为模 的 完全 剩余系,则:为模
的 完全 剩余系。
证明
只需证明对任意满足
实际上,由
进一步,
因此,
若
,令 分别为模 的 既约 剩余系,则:为模
的 既约 剩余系。
Tip
该定理等价于证明 Euler 函数为 积性函数。
证明
令
为模
显然
任取
因此可得
任取
因此可得
综上所述,
为模
数论函数
数论函数(也称算数函数)指定义域为正整数的函数。数论函数也可以视作一个数列。
积性函数
定义
在数论中,若函数
在数论中,若函数
性质
若
对正整数
若
若
例子
- 单位函数:
。(完全积性) - 恒等函数:
, 通常简记作 。(完全积性) - 常数函数:
。(完全积性) - 除数函数:
。 通常简记作 或 , 通常简记作 。 - 欧拉函数:
。 - 莫比乌斯函数:
,其中 表示 的本质不同质因子个数。
加性函数
定义
在数论中,若函数
在数论中,若函数
加性函数
本节中的加性函数指数论上的加性函数 (Additive function),应与代数中的 Additive map 做区分。
性质
对正整数
若
若
例子
为方便叙述,令所有质数组成的集合为
- 所有质因子数目:
。(完全加性) - 相异质因子数目:
。 - 所有质因子之和:
。(完全加性) - 相异质因子之和:
。
参考资料与注释
- 潘承洞,潘承彪。初等数论。北京大学出版社。
本页面最近更新:2024/10/6 22:16:34,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:383494, buuzzing, Emp7iness, Enter-tainer, Great-designer, jifbt, jiyu596, Kaiser-Yang, Koishilll, ksyx, Marcythm, oosquare, Qiu-Quanzhi, Saisyc, sshwy, Tiphereth-A, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用