数论基础
本文对于数论的开头部分做一个简介。
整除¶
整除的定义:设
整除的性质:
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
显然约数(显然因数):对于整数
对于整数
约数的性质:
- 设整数
b\ne0 d b \dfrac{b}{d} b - 设整数
b>0 d b \dfrac{b}{d} b
带余数除法¶
余数的定义:设
无论整数
一般情况下,
余数往往还有两种常见取法:
绝对最小余数:
最小正余数:
带余数除法的余数只有最小非负余数。如果没有特别说明,余数总是指最小非负余数。
余数的性质:
- 任一整数被正整数
a 0 (a-1) a - 相邻的
a a a a
最大公约数与最小公倍数¶
关于公约数、公倍数、最大公约数与最小公倍数,四个名词的定义,见 最大公约数。
互素¶
两个整数互素(既约)的定义:若
多个整数互素(既约)的定义:若
多个整数互素,不一定两两互素。例如
互素的性质与最大公约数理论:裴蜀定理(Bézout's identity)。见 裴蜀定理。
辗转相除法¶
辗转相除法是一种算法,也称 Euclid 算法。见 最大公约数。
素数与合数¶
关于素数的算法见 素数。
设整数
若整数
整数的因数是素数,则该素数称为该整数的素因数(素约数)。
素数与合数的简单性质:
- 大于
1 a a d e 1<d,e<a - 如果素数
p 1 d d=p - 大于
1 a - 对于合数
a p\le\sqrt{a} p\mid a - 素数有无穷多个。
- 所有大于
3 6n\pm 1
算术基本定理¶
算术基本引理:
设
算术基本引理是素数的本质属性,也是素数的真正定义。
上文给出的素数定义,事实上叫做不可约数,素数是不可约数的子集。在一些整环中,不可约数和素数是两个不同的集合,在两集合不相等的整环中,算术基本定理不成立。由于整数范围内两个集合完全一致,因此可以不做区分。
算术基本定理(唯一分解定理):
设正整数
其中
标准素因数分解式:
将上述表示中,相同的素数合并,可得:
称为正整数
算术基本定理和算术基本引理,两个定理是等价的。
同余¶
同余的定义:设整数
否则,
这样的等式,称为模
根据整除的性质,上述同余式也等价于
如果没有特别说明,模数总是正整数。
式中的
同余的性质:
- 自反性:
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) d m a,b d a,b
还有性质是乘法逆元。见 乘法逆元。
C/C++ 的整数除法和取模运算¶
在 C/C++ 中,整数除法和取模运算,与数学上习惯的取模和除法不一致。
对于所有标准版本的 C/C++,规定在整数除法中:
- 当除数为 0 时,行为未定义;
- 否则
(a / b) * b + a % b
的运算结果与a
相等。
也就是说,取模运算的符号取决于除法如何取整;而除法如何取整,这是实现定义的(由编译器决定)。
从 C992和 C++113标准版本起,规定 商向零取整(舍弃小数部分);取模的符号即与被除数相同。从此以下运算结果保证为真:
1 2 3 4 |
|
数论函数¶
数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。
积性函数¶
定义¶
若函数
若函数
性质¶
若
设
若
若
例子¶
- 单位函数:
\varepsilon(n)=[n=1] - 恒等函数:
\operatorname{id}_k(n)=n^k \operatorname{id}_{1}(n) \operatorname{id}(n) - 常数函数:
1(n)=1 - 除数函数:
\sigma_{k}(n)=\sum_{d\mid n}d^{k} \sigma_{0}(n) d(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) n
加性函数
此处加性函数指数论上的加性函数 (Additive function)。对于加性函数
参考资料与注释¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用