数论基础

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

整除

整除的性质：

• 
• 
• 
• 
• 设 ，那么 。
• 设 ，那么 。
• 设 ，那么 。

约数

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

平凡约数（平凡因数）：对于整数 ，、 是 的平凡约数。当 时， 只有两个平凡约数。

对于整数 ， 的其他约数称为真约数（真因数、非平凡约数、非平凡因数）。

约数的性质：

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

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

带余数除法

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

一般情况下， 取 ，此时等式 称为带余数除法（带余除法）。这里的余数 称为最小非负余数。

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

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

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

余数的性质：

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

最大公约数与最小公倍数

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

最大公约数有如下性质：

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

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

• 若 且 ，则 ；
• 若 、 且 ，则 ；
• 若 ，则 ；
• 若 ，则 。特别地，若 ，则 ；
• 对整数 ，若 ，且 ，则 。

最小公倍数有如下性质：

• ；
• ；
• 若 ，则 ；
• 若 ，则 ；
• 。进而 ；
• 若 ，则 ；
• ；
• ；
• 。

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

• ；
• ；
• 。

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

互素

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

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

辗转相除法

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

素数与合数

关于素数的算法见 素数。

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

整数的因数是素数，则该素数称为该整数的素因数（素约数）。

素数与合数的简单性质：

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

算术基本定理

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

算术基本定理（唯一分解定理）

设正整数 ，那么必有表示：

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

标准素因数分解式

将上述表示中，相同的素数合并，可得：

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

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

同余

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

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

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

同余的性质：

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

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

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

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

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

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

也就是说，取模运算的符号取决于除法如何取整；而除法如何取整，这是实现定义的（由编译器决定）。

从 C99²和 C++11³标准版本起，规定 商向零取整（舍弃小数部分）；取模的符号即与被除数相同。从此以下运算结果保证为真：

1
2
3
4

5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;

同余类与剩余系

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

• ；
• ；
• ；
• 。

由同余类的定义可知：

• ；
• ；
• 对任意 ，要么 ，要么 ；
• 若 ，则对任意整数 均有 。

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

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

不难发现：

• 对任意整数 ，；
• 对任意与 互质的整数 ，。

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

由 抽屉原理 可知：

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

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

我们还可以定义模 的：

• 最小非负（完全）剩余系：；
• 最小正（完全）剩余系：；
• 绝对最小（完全）剩余系：；
• 最大非正（完全）剩余系：；
• 最大负（完全）剩余系：。

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

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

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

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

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

由 抽屉原理 可知：

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

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

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

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

剩余系的复合

对正整数 ，我们有如下定理：

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

  

  为模 的 完全 剩余系。进而，若 ，令 分别为模 的 完全 剩余系，则：

  

  为模 的 完全 剩余系。

证明

只需证明对任意满足 的 ，，都有：

实际上，由 ，我们有 ，进而 ，由 可知 ，进而有 。

进一步，，则 ，即 。

因此，

• 若 ，令 分别为模 的 既约 剩余系，则：

  

  为模 的 既约 剩余系。

证明

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

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

显然 。

任取 ，其中 且 ，有 ，由 可得

因此可得 且 ，即 。

任取 ，其中 且 ，有 且 ，由 可得

因此可得 ，即 。

综上所述，

为模 的 既约 剩余系。

数论函数

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

积性函数

性质

若 和 均为积性函数，则以下函数也为积性函数：