数论基础

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

整除

整除的定义：设 $a,b\in\mathbf{Z}$ ， $a\ne 0$ 。如果 $\exists q\in\mathbf{Z}$ ，使得，那么就说可被整除，记作 $a\mid b$ ；不被整除记作 $a\nmid b$ 。

整除的性质：

$a\mid b\iff-a\mid b\iff a\mid-b\iff|a|\mid|b|$
$a\mid b\land b\mid c\implies a\mid c$
$a\mid b\land a\mid c\iff\forall x,y\in\mathbf{Z}, a\mid(xb+yc)$
$a\mid b\land b\mid a\implies b=\pm a$
设 $m\ne0$ ，那么 $a\mid b\iff ma\mid mb$ 。
设 $b\ne0$ ，那么 $a\mid b\implies|a|\le|b|$ 。
设 $a\ne0,b=qa+c$ ，那么 $a\mid b\iff a\mid c$ 。

约数（因数）：若 $a\mid b$ ，则称是的倍数，是的约数。

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

平凡约数（平凡因数）：对于整数 $b\ne0$ ， $\pm1$ 、 $\pm b$ 是的平凡约数。当 $b=\pm1$ 时，只有两个平凡约数。

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

约数的性质：

设整数 $b\ne0$ 。当遍历的全体约数的时候， $\dfrac{b}{d}$ 也遍历的全体约数。
设整数 $b\gt 0$ ，则当遍历的全体正约数的时候， $\dfrac{b}{d}$ 也遍历的全体正约数。

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

带余数除法

余数的定义：设为两个给定的整数， $a\ne0$ 。设是一个给定的整数。那么，一定存在唯一的一对整数和，满足 $b=qa+r,d\le r<|a|+d$ 。

无论整数取何值，统称为余数。 $a\mid b$ 等价于 $a\mid r$ 。

一般情况下，取，此时等式 $b=qa+r,0\le r<|a|$ 称为带余数除法（带余除法）。这里的余数称为最小非负余数。

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

绝对最小余数：取的绝对值的一半的相反数。即 $b=qa+r,-\dfrac{|a|}{2}\le r<|a|-\dfrac{|a|}{2}$ 。

最小正余数：取。即 $b=qa+r,1\le r<|a|+1$ 。

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

余数的性质：

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

最大公约数与最小公倍数

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

互素

两个整数互素（既约）的定义：若 $\gcd(a_1,a_2)=1$ ，则称和互素（既约）。

多个整数互素（既约）的定义：若 $\gcd(a_1,\ldots,a_k)=1$ ，则称 $a_1,\ldots,a_k$ 互素（既约）。

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

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

辗转相除法

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

素数与合数

关于素数的算法见素数。

设整数 $p\ne0,\pm1$ 。如果除了平凡约数外没有其他约数，那么称为素数（不可约数）。

若整数 $a\ne0,\pm 1$ 且不是素数，则称为合数。

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

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

素数与合数的简单性质：

大于的整数是合数，等价于可以表示为整数和（）的乘积。
如果素数有大于的约数，那么。
大于的整数一定可以表示为素数的乘积。
对于合数，一定存在素数 $p\le\sqrt{a}$ 使得 $p\mid a$ 。
素数有无穷多个。
所有大于的素数都可以表示为 $6n\pm 1$ 的形式¹。

算术基本定理

算术基本引理：

设是素数， $p\mid a_1a_2$ ，那么 $p\mid a_1$ 和 $p\mid a_2$ 至少有一个成立。

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

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

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

a=p_1p_2\cdots p_s

其中 $p_j(1\le j\le s)$ 是素数。并且在不计次序的意义下，该表示唯一。

标准素因数分解式：

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

a={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_s}^{\alpha_s},p_1<p_2<\cdots<p_s

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

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

同余

同余的定义：设整数 $m\ne0$ 。若 $m\mid(a-b)$ ，称为模数（模），同余于模，是对模的剩余。记作 $a\equiv b\pmod m$ 。

否则，不同余于模，不是对模的剩余。记作 $a\not\equiv b\pmod m$ 。

这样的等式，称为模的同余式，简称同余式。

根据整除的性质，上述同余式也等价于 $a\equiv b\pmod{(-m)}$ 。

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

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

同余的性质：

自反性： $a\equiv a\pmod m$ 。
对称性：若 $a\equiv b\pmod m$ ，则 $b\equiv a\pmod m$ 。
传递性：若 $a\equiv b\pmod m,b\equiv c\pmod m$ ，则 $a\equiv c\pmod m$ 。
线性运算：若 $a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$ 则有：
- $a\pm c\equiv b\pm d\pmod m$ 。
- $a\times c\equiv b\times d\pmod m$ 。
若 $a,b\in\mathbf{Z},k,m\in\mathbf{N}^*,a\equiv b\pmod m$ , 则 $ak\equiv bk\pmod{mk}$ 。
若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m$ ，则当 $a\equiv b\pmod m$ 成立时，有 $\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)$ 。
若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid m$ ，则当 $a\equiv b\pmod m$ 成立时，有 $a\equiv b\pmod d$ 。
若 $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*$ ，则当 $a\equiv b\pmod m$ 成立时，有 $\gcd(a,m)=\gcd(b,m)$ 。若能整除及中的一个，则必定能整除中的另一个。

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

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;

数论函数

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

积性函数

定义

若函数满足且 $\forall x,y\in\mathbf{N}^*,\gcd(x,y)=1$ 都有，则为积性函数。

若函数满足且 $\forall x,y\in\mathbf{N}^*$ 都有，则为完全积性函数。

性质

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

\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g\left(\dfrac{x}{d}\right) \end{aligned}

设 $x=\prod p_i^{k_i}$

若为积性函数，则有 $F(x)=\prod F(p_i^{k_i})$ 。

若为完全积性函数，则有 $F(x)=\prod F(p_i)^{k_i}$ 。

例子

单位函数： $\varepsilon(n)=[n=1]$ 。（完全积性）
恒等函数： $\operatorname{id}_k(n)=n^k$ ， $\operatorname{id}_{1}(n)$ 通常简记作 $\operatorname{id}(n)$ 。（完全积性）
常数函数：。（完全积性）
除数函数： $\sigma_{k}(n)=\sum_{d\mid n}d^{k}$ 。 $\sigma_{0}(n)$ 通常简记作或 $\tau(n)$ ， $\sigma_{1}(n)$ 通常简记作 $\sigma(n)$ 。
欧拉函数： $\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]$
莫比乌斯函数： $\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$ ，其中 $\omega(n)$ 表示的本质不同质因子个数，它是一个加性函数。

加性函数

此处加性函数指数论上的加性函数 (Additive function)。对于加性函数，当整数互质时，均有。应与代数中的加性函数 (Additive map) 区分。

参考资料与注释

本页面最近更新：2023/3/1 01:11:07，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：383494, buuzzing, ctj12461, Emp7iness, Enter-tainer, Great-designer, jifbt, jiyu596, Koishilll, ksyx, Saisyc, sshwy, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用