本文对于数论的开头部分做一个简介。
符号
整除/同余理论常见符号
- 整除符号：\(x|y\)，表示\(x\) 整除\(y\)，即\(x\) 是\(y\) 的因数。
- 取模符号：\(x \bmod y\)，表示\(x\) 除以\(y\)得到的余数。
- 互质符号：\(x \perp y\)，表示\(x,y\) 互质。
- 最大公约数：\(gcd(x, y)\)，在无混淆意义的时侯可以写作\((x, y)\)。
- 最小公倍数：\(lcm(x, y)\)，在无混淆意义的时侯可以写作\([x, y]\)。
数论函数常见符号
求和符号：\(\sum\)符号，表示满足特定条件的数的和。举几个例子：
• \(\sum_{i=1}^{n}{i}\)表示\(1+2+…+n\)的和。其中\(i\)是一个变量，在求和符号的意义下\(i\)通常是正整数或者非负整数（除非特殊说明）。这个式子的含义可以理解为，\(i\)从\(1\)循环到\(n\)，所有\(i\)的和。这个式子用代码的形式很容易表达。当然，学过简单的组合数学的同学都知道\(\sum_{i=1}^{n}{i}=\frac{n(n+1)}{2}\)。
• \(\sum_{S \subseteq T}{|S|}\)表示所有被\(T\)包含的集合的大小的和。
• \(\sum_{p \leq n, p\perp n}{1}\) 表示的是\(n\)以内有多少个与\(n\)互质的数，即\(\varphi(n)\)，\(\varphi\) 是欧拉函数。
求积符号：\(\prod\)符号，表示满足特定条件的数的积。举几个例子：
• \(\prod_{i=1}^{n}{i}\)表示\(n\)的阶乘，即\(n!\)。在组合数学常见符号中会讲到。
• \(\prod_{i=1}^{n}{a_i}\)表示\(a_{1}\times a_{2}\times a_{3}\times …\times a_{n}\)。
• \(\prod_{x|d}{x}\)表示\(d\)的所有因数的乘积。
在行间公式中，求和符号与求积符号的上下条件会放到符号的上面和下面，这一点要注意。
其他常见符号
- 阶乘符号\(!\)，\(n!\)表示\(1\times 2\times 3\times…\times n\)。特别地，\(0! = 1\)。
- 向下取整符号：\(\lfloor x \rfloor\)，表示小于等于\(x\)的最大的整数。常用于分数，比如分数的向下取整\(\lfloor \frac{x}{y} \rfloor\)。
- 向上取整符号：\(\lceil x \rceil\)，与向下取整符号相对，表示大于等于\(x\)的最小的整数。
整除
整除的定义： 设 𝑎, 𝑏 ∈ Z，𝑎 ≠ 0。如果 ∃𝑞 ∈ Z，使得 𝑏 = 𝑎𝑞，那么就说 𝑏 可被 𝑎 整除，记作 𝑎 ∣ 𝑏，且称 𝑏 是 𝑎 的倍数，𝑎 是 𝑏 的约数（因数）。
𝑏 不被 𝑎 整除记作 𝑎 ∤ 𝑏。
整除的性质：
• 𝑎 ∣ 𝑏 ⟺ −𝑎 ∣ 𝑏 ⟺ 𝑎 ∣ −𝑏 ⟺ |𝑎| ∣ |𝑏|
• 𝑎 ∣ 𝑏 ∧ 𝑏 ∣ 𝑐 ⟹ 𝑎 ∣ 𝑐
• 𝑎 ∣ 𝑏 ∧ 𝑎 ∣ 𝑐 ⟺ ∀𝑥, 𝑦 ∈ Z, 𝑎 ∣ (𝑥𝑏 + 𝑦𝑐)
• 𝑎 ∣ 𝑏 ∧ 𝑏 ∣ 𝑎 ⟹ 𝑏 = ±𝑎
• 设 𝑚 ≠ 0，那么 𝑎 ∣ 𝑏 ⟺ 𝑚𝑎 ∣ 𝑚𝑏。
• 设 𝑏 ≠ 0，那么 𝑎 ∣ 𝑏 ⟹ |𝑎| ≤ |𝑏|。
• 设 𝑎 ≠ 0, 𝑏 = 𝑞𝑎 + 𝑐，那么 𝑎 ∣ 𝑏 ⟺ 𝑎 ∣ 𝑐。
0 是所有非 0 整数的倍数。对于整数 𝑏 ≠ 0，𝑏 的约数只有有限个。
显然约数（显然因数）：对于整数 𝑏 ≠ 0，±1、±𝑏 是 𝑏 的显然约数。当 𝑏 = ±1 时，𝑏 只有两个显然约数。
对于整数 𝑏 ≠ 0，𝑏 的其他约数称为真约数（真因数、非显然约数、非显然因数）。
约数的性质：
• 设整数 𝑏 ≠ 0。当 𝑑 遍历 𝑏 的全体约数的时候， \(\frac{b}{d}\)也遍历 𝑏 的全体约数。
• 设整数 𝑏 > 0，则当 𝑑 遍历 𝑏 的全体正约数的时候， \(\frac{b}{d}\)也遍历 𝑏 的全体正约数。
带余数除法
余数的定义： 设 𝑎, 𝑏 为两个给定的整数，𝑎 ≠ 0。设 𝑑 是一个给定的整数。那么，一定存在唯一的一对整数 𝑞 和 𝑟，满足 𝑏 = 𝑞𝑎 + 𝑟, 𝑑 ≤ 𝑟 < |𝑎| + 𝑑。
无论整数 𝑑 取何值，𝑟 统称为余数。𝑎 ∣ 𝑏 等价于 𝑎 ∣ 𝑟。
一般情况下，𝑑 取 \(0\)，此时等式 𝑏 = 𝑞𝑎 + 𝑟, 0 ≤ 𝑟 < |𝑎| 称为带余数除法（带余除法）。这里的余数 𝑟 称为最小非负余数。
余数往往还有两种常见取法：
绝对最小余数：𝑑 取 𝑎 的绝对值的一半的相反数。即\(b = qa + r,-\frac{|a|}{2}\leq r <|a|-\frac{|a|}{2}\)。
最小正余数：𝑑 取 1。即 𝑏 = 𝑞𝑎 + 𝑟, 1 ≤ 𝑟 < |𝑎| + 1。
带余数除法的余数只有最小非负余数。如果没有特别说明，余数总是指最小非负余数。
余数的性质：
• 任一整数被正整数 𝑎 除后，余数一定是且仅是 0 到 (𝑎 − 1) 这 𝑎 个数中的一个。
• 相邻的 𝑎 个整数被正整数 𝑎 除后，恰好取到上述 𝑎 个余数。特别地，一定有且仅有一个数被 𝑎 整除。
最大公约数与最小公倍数
关于公约数、公倍数、最大公约数与最小公倍数，四个名词的定义，这里暂时不赘述，详情可参见别的博客。
互素
两个整数互素（既约）的定义：若 gcd(𝑎1 , 𝑎2 ) = 1，则称 𝑎1 和 𝑎2 互素（既约）。
多个整数互素（既约）的定义：若 gcd(𝑎1 , … , 𝑎𝑘 ) = 1，则称 𝑎1 , … , 𝑎𝑘 互素（既约）。
多个整数互素，不一定两两互素。例如 6、10 和 15 互素，但是任意两个都不互素。
互素的性质与最大公约数理论：裴蜀定理（Bézout’s identity）。见 裴蜀定理。
辗转相除法
辗转相除法是一种算法，也称 Euclid 算法。
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a%b);
}
素数与合数
设整数 𝑝 ≠ 0, ±1。如果 𝑝 除了显然约数外没有其他约数，那么称 𝑝 为素数（不可约数）。
若整数 𝑎 ≠ 0, ±1 且 𝑎 不是素数，则称 𝑎 为合数。
𝑝 和 −𝑝 总是同为素数或者同为合数。如果没有特别说明，素数总是指正的素数。
整数的因数是素数，则该素数称为该整数的素因数（素约数）。
素数与合数的简单性质：
• 大于 1 的整数 𝑎 是合数，等价于 𝑎 可以表示为整数 𝑑 和 𝑒（1 < 𝑑, 𝑒 < 𝑎）的乘积。
• 如果素数 𝑝 有大于 1 的约数 𝑑，那么 𝑑 = 𝑝。
• 大于 1 的整数 𝑎 一定可以表示为素数的乘积。
• 对于合数 𝑎，一定存在素数 𝑝 ≤ √𝑎 使得 𝑝 ∣ 𝑎。
• 素数有无穷多个。
• 所有大于 3 的素数都可以表示为 6𝑛 ± 1 的形式。
算术基本定理
算术基本引理：
设 𝑝 是素数，\(p|a_{1}a_{2}\)，那么\(p|a_{1}\)和\(p|a_{2}\)至少有一个成立。
算术基本引理是素数的本质属性，也是素数的真正定义。
上文给出的素数定义，事实上叫做不可约数，素数是不可约数的子集。在一些整环中，不可约数和素数是两个不同的集合，在两集合不相等的整环中，算术基本定理不成立。由于整数范围内两个集合完全一致，因此可以不做区分。
算术基本定理（唯一分解定理）：
设正整数 𝑎，那么必有表示：
其中\(p_{j}(1\leq j\leq s)\)是素数。并且在不计次序的意义下，该表示唯一。
标准素因数分解式：
将上述表示中，相同的素数合并，可得：
称为正整数 𝑎 的标准素因数分解式。
算术基本定理和算术基本引理，两个定理是等价的。
同余
同余的定义：设整数 𝑚 ≠ 0。若 𝑚 ∣ (𝑎 − 𝑏)，称 𝑚 为模数（模），𝑎 同余于 𝑏 模 𝑚，𝑏 是 𝑎 对模 𝑚 的剩余。记作\(a \equiv b (\bmod m)\)
否则，𝑎 不同余于 𝑏 模 𝑚，𝑏 不是 𝑎 对模 𝑚 的剩余。记作 \(a\not\equiv b(\bmod m)\)。
这样的等式，称为模 𝑚 的同余式，简称同余式。
根据整除的性质，上述同余式也等价于\(a\equiv b(\bmod (-m))\).
如果没有特别说明，模数总是正整数。
式中的 𝑏 是 𝑎 对模 𝑚 的剩余，这个概念与余数完全一致。通过限定 𝑏 的范围，相应的有 𝑎 对模 𝑚 的最小非负剩余、绝对最小剩余、最小正剩余。
同余的性质：
• 自反性： \(a\equiv a (\bmod m)\)。
• 对称性：若 \(a\equiv b (\bmod m)\)，则 \(b\equiv a (\bmod m)\)。
• 传递性：若 \(a\equiv b (\bmod m)\), \(b\equiv c (\bmod m)\)，则 \(a\equiv c (\bmod m)\)。
• 线性运算：若 𝑎, 𝑏, 𝑐, 𝑑 ∈ Z, 𝑚 ∈ N∗ , \(a\equiv b (\bmod m)\), \(c\equiv d (\bmod m)\) 则有：
– \(a\pm c \equiv b \pm d (\bmod m)\)
– \(a\times c\equiv b \times d (\bmod m)\)
• 若 𝑎, 𝑏 ∈ Z, 𝑘, 𝑚 ∈ N∗ , \(a\equiv b(\bmod m)\), 则 \(ak\equiv bk(\bmod mk)\)。
• 若 𝑎, 𝑏 ∈ Z, 𝑑, 𝑚 ∈ N∗ , 𝑑 ∣ 𝑎, 𝑑 ∣ 𝑏, 𝑑 ∣ 𝑚，则当\(a\equiv b(\bmod m)\)成立时，有\(\frac{a}{d}\equiv \frac{b}{d}(\bmod \frac{m}{d})\)。
• 若 𝑎, 𝑏 ∈ Z, 𝑑, 𝑚 ∈ N∗ , 𝑑 ∣ 𝑚，则当\(a\equiv b(\bmod m)\) 成立时，有\(a\equiv b(\bmod d)\)。
• 若 𝑎, 𝑏 ∈ Z, 𝑑, 𝑚 ∈ N∗，则当\(a\equiv b(\bmod 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.
数论函数
数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。
积性函数
定义
若函数\(f(n)\)满足\(f(1)=1\) 且 ∀𝑥, 𝑦 ∈ N∗, \(gcd(x, y)=1\) 都有\(f(xy)=f(x)f(y)\)，则\(f(n)\)为积性函数。
若函数\(f(n)\)满足\(f(1)=1\)且 ∀𝑥, 𝑦 ∈ N∗ 都有\(f(xy)=f(x)f(y)\)，则\(f(n)\)为完全积性函数。
性质
若 𝑓(𝑥) 和 𝑔(𝑥) 均为积性函数，则以下函数也为积性函数：
设\(x=\prod p_i^{k_i}\)
若\(F(x)\)为积性函数，则有\(F(x)=\prod F(p_i^{k_i})\)。
若\(F(x)\)为完全积性函数，则有\(F(x)=\prod F(p_i)^{k_i}\)。
例子
• 单位函数：\(\epsilon (n)=[n=1]\)。（完全积性）
• 恒等函数：\(id_k(n)=n^k\)，\(id_1(n)\)通常简记作\(di(n)\)。（完全积性）
• 常数函数：\(1(n)=1\)。（完全积性）
• 除数函数：\(\sigma_k(n)=\sum_{d|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}|n,\\ (-1)^{w(n)} &otherwise\end{cases}\) 其中 𝜔(𝑛) 表示 𝑛 的本质不同质因子个数，它是一个加性函数。
原文地址：http://www.cnblogs.com/HuParry/p/16797588.html
