数论基础 | 您所在的位置:网站首页 › 0可以被正整数整除吗 › 数论基础 |
数论基础 本文对于数论的开头部分做一个简介。 整除定义设 ,。如果 ,使得 ,那么就说 可被 整除,记作 ; 不被 整除记作 。 整除的性质: 设 ,那么 。设 ,那么 。设 ,那么 。约数定义若 ,则称 是 的 倍数, 是 的 约数。 是所有非 整数的倍数。对于整数 , 的约数只有有限个。 平凡约数(平凡因数):对于整数 ,、 是 的平凡约数。当 时, 只有两个平凡约数。 对于整数 , 的其他约数称为真约数(真因数、非平凡约数、非平凡因数)。 约数的性质: 设整数 。当 遍历 的全体约数的时候, 也遍历 的全体约数。设整数 ,则当 遍历 的全体正约数的时候, 也遍历 的全体正约数。在具体问题中,如果没有特别说明,约数总是指正约数。 带余数除法余数设 为两个给定的整数,。设 是一个给定的整数。那么,一定存在唯一的一对整数 和 ,满足 。 无论整数 取何值, 统称为余数。 等价于 。 一般情况下, 取 ,此时等式 称为带余数除法(带余除法)。这里的余数 称为最小非负余数。 余数往往还有两种常见取法: 绝对最小余数: 取 的绝对值的一半的相反数。即 。最小正余数: 取 。即 。带余数除法的余数只有最小非负余数。如果没有特别说明,余数总是指最小非负余数。 余数的性质: 任一整数被正整数 除后,余数一定是且仅是 到 这 个数中的一个。相邻的 个整数被正整数 除后,恰好取到上述 个余数。特别地,一定有且仅有一个数被 整除。最大公约数与最小公倍数关于公约数、公倍数、最大公约数与最小公倍数,四个名词的定义,见 最大公约数。 Warning一些作者认为 和 的最大公约数无定义,其余作者一般将其视为 。C++ STL 的实现中采用后者,即认为 和 的最大公约数为 4。 最大公约数有如下性质: ;;若 ,则 ;;。进而 ;对不全为 的整数 和非零整数 ,;对不全为 的整数 ,若 ,则 ;。最大公约数还有如下与互素相关的性质: 若 且 ,则 ;若 、 且 ,则 ;若 ,则 ;若 ,则 。特别地,若 ,则 ;对整数 ,若 ,且 ,则 。最小公倍数有如下性质: ;;若 ,则 ;若 ,则 ;。进而 ;若 ,则 ;;;。最大公约数和最小公倍数可以组合出很多奇妙的等式,如: ;;。这些性质均可通过定义或 唯一分解定理 证明,其中使用唯一分解定理的证明更容易理解。 互素定义若 ,则称 和 互素(既约)。 若 ,则称 互素(既约)。 多个整数互素,不一定两两互素。例如 、 和 互素,但是任意两个都不互素。 互素的性质与最大公约数理论:裴蜀定理(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 45 % 3 == 2; 5 % -3 == 2; -5 % 3 == -2; -5 % -3 == -2; 同余类与剩余系为方便讨论,对集合 和元素 ,我们引入如下记号: ;;;。同余类对非零整数 ,把全体整数分成 个两两不交的集合,且同一个集合中的任意两个数模 均同余,我们把这 个集合均称为模 的 同余类 或 剩余类。用 表示含有整数 的模 的同余类。 不难证明对任意非零整数 ,上述划分方案一定存在且唯一。 由同余类的定义可知: ;;对任意 ,要么 ,要么 ;若 ,则对任意整数 均有 。注意到同余是等价关系,所以同余类即为同余关系的等价类。 我们把模 的同余类全体构成的集合记为 ,即 不难发现: 对任意整数 ,;对任意与 互质的整数 ,。由 商群 的定义可知 ,所以有时我们也会用 表示 。 由 抽屉原理 可知: 任取 个整数,必有两个整数模 同余。存在 个两两模 不同余的整数。由此我们给出完全剩余系的定义: (完全)剩余系对 个整数 ,若对任意的数 ,有且仅有一个数 使得 与 模 同余,则称这 个整数 为模 的 完全剩余系,简称 剩余系。 我们还可以定义模 的: 最小非负(完全)剩余系:;最小正(完全)剩余系:;绝对最小(完全)剩余系:;最大非正(完全)剩余系:;最大负(完全)剩余系:。若无特殊说明,一般我们只用最小非负剩余系。 我们注意到如下命题成立: 在模 的任意一个同余类中,任取两个整数 均有 。考虑同余类 ,若 ,则该同余类的所有元素均与 互质,这说明我们也许可以通过类似方式得知所有与 互质的整数构成的集合的结构。 既约同余类对同余类 ,若 ,则称该同余类为 既约同余类 或 既约剩余类。 我们把模 既约剩余类的个数记作 ,称其为 Euler 函数。 我们把模 的既约同余类全体构成的集合记为 ,即 Warning对于任意的整数 和与 互质的整数 ,,但是 不一定为 。这一点与 不同。 由 抽屉原理 可知: 任取 个与 互质的整数,必有两个整数模 同余。存在 个与 互质且两两模 不同余的整数。由此我们给出既约剩余系的定义: 既约剩余系对 个整数 ,若 ,且对任意满足 的数 ,有且仅有一个数 使得 与 模 同余,则称这 个整数 为模 的 既约剩余系、缩剩余系 或 简化剩余系。 类似地,我们也可以定义最小非负既约剩余系等概念。 若无特殊说明,一般我们只用最小非负既约剩余系。 剩余系的复合对正整数 ,我们有如下定理: 若 ,令 分别为模 的 完全 剩余系,则对任意与 互质的 均有: 为模 的 完全 剩余系。进而,若 ,令 分别为模 的 完全 剩余系,则: 为模 的 完全 剩余系。 证明只需证明对任意满足 的 ,,都有: 实际上,由 ,我们有 ,进而 ,由 可知 ,进而有 。 进一步,,则 ,即 。 因此, 若 ,令 分别为模 的 既约 剩余系,则: 为模 的 既约 剩余系。 Tip该定理等价于证明 Euler 函数为 积性函数。 证明令 分别为模 的完全剩余系,我们已经证明了 为模 的完全剩余系。令 ,显然 为模 的既约剩余系,所以我们只需证明 即可。 显然 。 任取 ,其中 且 ,有 ,由 可得 因此可得 且 ,即 。 任取 ,其中 且 ,有 且 ,由 可得 因此可得 ,即 。 综上所述, 为模 的 既约 剩余系。 数论函数数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。 积性函数定义若函数 满足 且 都有 ,则 为 积性函数。 若函数 满足 且 都有 ,则 为 完全积性函数。 性质若 和 均为积性函数,则以下函数也为积性函数: 设 若 为积性函数,则有 。 若 为完全积性函数,则有 。 例子单位函数:。(完全积性)恒等函数:, 通常简记作 。(完全积性)常数函数:。(完全积性)除数函数:。 通常简记作 或 , 通常简记作 。欧拉函数:莫比乌斯函数:,其中 表示 的本质不同质因子个数,它是一个加性函数。加性函数此处加性函数指数论上的加性函数 (Additive function)。对于加性函数 ,当整数 互质时,均有 。 应与代数中的加性函数 (Additive map) 区分。 参考资料与注释潘承洞,潘承彪。初等数论。北京大学出版社。Are all primes (past 2 and 3) of the forms 6n+1 and 6n-1? ↩ Arithmetic operators (C) - cppreference.com ↩ Arithmetic operators (C++) - cppreference.com ↩ std::gcd - cppreference.com ↩ 本页面最近更新:2024/7/4 09:54:13,更新历史发现错误?想一起完善? 在 GitHub 上编辑此页!本页面贡献者:383494, buuzzing, Emp7iness, Enter-tainer, Great-designer, jifbt, jiyu596, Kaiser-Yang, Koishilll, ksyx, oo-infty, Saisyc, sshwy, Tiphereth-A, xyf007本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用 |
CopyRight 2018-2019 实验室设备网 版权所有 |