# 数论基础
## 整除、同余和质数
**取模**：若 $a\div m = c \cdots r,\ a,b,c,r\in \mathbb{Z}$，则记 $a \bmod m = r$
**四则运算取模的性质**：
1. $(a\pm b)\bmod m = [(a\bmod m)\pm(b\bmod m)]\bmod m$
2. $(ab)\bmod m = [(a\bmod m)(b\bmod m)]\bmod m$
3. $\displaystyle(\frac{a}{b})\bmod m = (\frac{a}{b}bb^{-1})\bmod m = (ab^{-1})\bmod m$，不可直接将取模下放至分子分母
**整除**：若 $a\bmod m = 0$，则称$m$整除$a$，记为$m|a$
**同余的定义**：若 $a\bmod m = r$，且 $b\bmod m = r$, 则称 $a$ 与 $b$ 关于 $m$ 同余，记为 $a\equiv b \pmod m$。
易知 $a \bmod m = r$ 有一种等价写法为 $a\equiv r \pmod m$
同余是一种等价关系，满足自反对称传递，对 $i\in\{0.1,2,\dots,m-1\}$，每个 $[i]_{\bmod m} = \left\{i+km : k\in \mathbb{Z}\right\}$ 为模 $m$ 时的同余等价类，简称同余类，可将 $i$ 作为同余类的代表元。
**同余的性质**：
1. $a\equiv b \pmod m\ \Leftrightarrow\ m|(a-b)$
2. $a\equiv b \pmod m\ \Leftrightarrow\ a\bmod m=b\bmod m$
3. $a\equiv b \pmod m\ \Rightarrow\ \gcd(a,m)=\gcd(b,m)$
- 反之不然（如$a=14,b=22,m=10$）
4. $a\equiv b \pmod m\ 且\ d|m\ \Rightarrow\ a\equiv b \pmod d$
- 反之不然（如$a=7, b=2, d=5, m=10$）
- $x\equiv a \pmod m\ 且\ m=p_1p_2\cdots p_k$，$p_i$为质数且两两不同 $\Leftrightarrow\ \begin{cases}x\equiv a\pmod{p_1}\\ x\equiv a\pmod{p_2}\\\;\vdots\\ x\equiv a\pmod{p_k}\end{cases}$
5. $a\equiv 1 \pmod m \Rightarrow \gcd(a,m)=1$
- 反之不然（如$a=15,m=17$）
6. $a\equiv b \pmod m\ 且\ c\equiv d\pmod m\\1)\ \Rightarrow\ a\pm c \equiv b\pm d \pmod m\\2)\ \Rightarrow\ ac \equiv bd \pmod m$
7. $ac\equiv bc \pmod m\ \Rightarrow a \equiv b \pmod {\frac{m}{\gcd(c,m)}}$
**质数**：对 $p>1\in\mathbb{N}_+$，若对所有 $x$ 都有 $\gcd(x,p) =1$（$1<x<p$），则称 $p$ 为质数
> 欧拉筛法求质数：（埃氏筛法简单但速度慢）
**互质**：对 $a,b\in\mathbb{N}_+$，若 $\gcd(a,b)=1$，则称 $a,b$ 互质。在此定义下 $1$ 与任何正整数互质。
**逆元（数论倒数）**：对整数 $a\ne 0$ 且 $\gcd(a,m)=1$，若有 $aa^{-1}\equiv 1\pmod m$，称$a$和$a^{-1}$互逆，$a^{-1}$为$a$的一个逆元。对带模除法必用！（见上方四则运算）
## 欧拉函数、欧拉定理、费马小定理
**算术基本定理**：对于 $\forall n>1\in\mathbb{N}_+$，有$n=p_1^{\displaystyle \varepsilon_1}p_2^{\displaystyle \varepsilon_2}\cdots p_n^{\displaystyle \varepsilon_n}$，$p_i$是互不相同的质数。可以简单理解为短除法必定有解且唯一。
> 求解质数分解，需要质数筛+线性遍历短除法
**欧拉函数**：对正整数 $n$，欧拉函数 $\varphi(n)$ 定义为小于等于 $n$ 并与 $n$ 互质的正整数的个数。
**欧拉函数的性质**：
1. $\varphi(1)=1$。因小于等于1并与1互质的正整数有：{1}。这也是唯一取定义中的等号的情况。
2. 若$p$为质数，则 $\varphi(p)=p-1$。因小于等于$p$并与$p$互质的数有：{1, 2, ..., $p-1$}
3. $\varphi(m) = \left|\left\{[i]_{\bmod m} : \gcd(i, m) = 1\right\}\right|$，即$m$的既约同余类个数
- 由鸽巢原理可知，任取 $\varphi(m)+1$ 个与$m$互质的数，必有至少两个整数模$m$同余
**欧拉定理**：对 $a,m\in\mathbb{N}_+$ 且 $a,m$ 互质，有$a^{\varphi(m)}\equiv 1 \pmod m$
**扩展欧拉定理**：$a^b\equiv a^{b\bmod \varphi(m)} \pmod m$，可用于带模降幂
例题演示：
- $a^{\sum_{k|n}{n\choose k}}\bmod{8971} = a^{\sum_{k|n}{n\choose k}\bmod{8970}}\bmod{8971}$
- $8970=2\times3\times5\times13\times23$，恰好分解为无重复的素数乘积，由同余的性质4将同余方程 $x\equiv \sum_{k|n}{n\choose k}\pmod{8970}$ 拆解为同余方程组：
- $\begin{cases}x\equiv \sum_{k|n}{n\choose k}\pmod{2}\\ x\equiv \sum_{k|n}{n\choose k}\pmod{3}\\ x\equiv \sum_{k|n}{n\choose k}\pmod{5}\\ x\equiv \sum_{k|n}{n\choose k}\pmod{13}\\ x\equiv \sum_{k|n}{n\choose k}\pmod{23}\end{cases}$
- 最后利用中国剩余定理求解，得到一个解 $x_0$，再带入原式求 $a^{x_0}\bmod 8971$
**费马小定理**：当欧拉定理中$m$取一质数$p$时，有$a^{p-1}\equiv 1 \pmod m$
**利用欧拉定理或费马小定理求逆元**：
- 由于 $a\cdot a^{\varphi(m)-1}\equiv 1 \pmod m$，可得 $a^{\varphi(m)-1}$ 为 $a$ 的逆元。在 $a,m$ 互质时可用
- 在$m$为质数时，$a^{m-2}$ 为 $a$ 的逆元，可以用快速幂求解。
```cpp
ll inv(ll a, ll m) {
return qpow_mod(a, m-2, m);
}
```
## GCD、LCM
**欧几里得算法（辗转相除法）求最大公约数**：
```cpp
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// 也可使用：std::__gcd(a, b)
```
**计算最小公倍数**：$\displaystyle \text{lcm}(a,b)=\frac{a\cdot b}{\gcd(a,b)}$
```cpp
ll lcm(ll a, ll b) {
return a / gcd(a,b) * b
}
```
多个数的情况：多个数的最大公约数是从前向后两两逐个计算最大公约数的结果。最小公倍数类似。
**GCD和LCM的性质**：
- $\displaystyle \text{lcm}(a,b)=\frac{a\cdot b}{\gcd(a,b)}$
- 对 $\forall m\in\mathbb{N}_+$，有：
- $\gcd(ma_1,ma_2,\dots,ma_n)=m\cdot \gcd(a_1,a_2,\dots,a_n)$
- $\text{lcm}(ma_1,ma_2,\dots,ma_n)=m\cdot \text{lcm}(a_1,a_2,\dots,a_n)$
- 若 $\gcd(a_1,a_2,\dots,a_n)=x$，则 $\gcd(\frac{a_1}{x},\frac{a_2}{x},\dots,\frac{a_n}{x})=1$
## Ext_GCD（扩展欧几里得）
**扩展欧几里得算法**：递归辗转相除得到两数的GCD后，再逆推，得到原始输入两数的线性组合来表示GCD：
```cpp
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll res = ext_gcd(b, a % b, x, y);
ll t = x;
x = y;
y = t - (a / b) * y;
return res;
}
```
见如下例子：
```text
a b c r |A x y x' r y' GCD
435 / 377 = 1 ... 58 || -6 7(= 1 - 1 * (-6)) = 29
377 / 58 = 6 ... 29 || 1 -6(= 0 - 6 * 1 ) = 29
58 / 29 = 2 ... 0 || 0 1(= 1 - 2 * 0 ) = 29
29 / 0 V| 1 0 = 29
从倒数第三行向上，可以理解为以下递推式：
GCD= a - c * b = a' - c'* ( a - c * b )
29 = 377 - 6 * 58 = 377 - 6 * (435 - 1 * 377)
= (-6)*435 + (1-1*(-6))*377
```
**现场推导比较困难，所以记住：`t=x; x=y; y=t-(a/b)*y;`**
**扩展欧几里得实质上是求如下不定方程的整数解，且其一定有解：**
$$
ax+by=\gcd(a,b)
$$
其中$x,y$为原输入$a,b$的线性组合系数（且是整数）。
**裴蜀定理**：$ax+by=c$ 有整数解，当且仅当 $\gcd(a,b)|c$
**用Ext_GCD可以解决的问题**：
1. 求解不定方程 $ax+by=\gcd(a,b)$ 的一个特解 $x_0, y_0$，这是Ext_GCD的标准用途
2. 求解不定方程 $ax+by=c$，$c$是$\gcd(a,b)$的倍数
- 验证 $\gcd(a,b)|c$
- 计算 $ax+by=\gcd(a,b)$ 的一个特解 $x_0, y_0$
- 推导可得 $\displaystyle a\frac{cx}{\gcd(a,b)}+b\frac{cy}{\gcd(a,b)}=c$
- 即原方程的一个特解为$\begin{cases}x'_0=\displaystyle \frac{c\cdot x_0}{\gcd(a,b)}\\ y'_0=\displaystyle \frac{c\cdot y_0}{\gcd(a,b)}\end{cases}$
- 代码为（注意结果可能在整个整数域）：
```cpp
ext_gcd(a, b, x, y);
x = c / gcd(a, b) * x;
y = c / gcd(a, b) * y;
```
3. 求解一元线性同余方程 $ax\equiv c\pmod m$
- 由 $m|(ax-c)$ 得 $ax-c=my$，y为一个倍数
- 整理得 $ax+m\bar{y}=c$，$\bar{y}=-y$
- 用Ext_GCD求解此方程，得到$x_0$和$\bar{y}_0$，$x_0$即为所求
- 代码为：
```cpp
ext_gcd(a, m, x, _y);
x = c / gcd(a, m) * x;
x = (x % m + m) % m; //确保取到同余且在0~m之间的代表元
```
4. 求 $a$ 的逆元 $a^{-1}$：
- 求解同余方程 $aa^{-1}\equiv 1 \pmod m$
- 即 $aa^{-1}+my=1$，这里 $\gcd(a,m)$ 恰好等于 $1$
- 代码为：
```cpp
ext_gcd(a, m, a_inv, y);
a_inv = (a_inv % m + m) % m; //确保取到同余且在0~m之间的代表元
```
> 同余方程 $ax\equiv b \pmod m$ 的特解 $x_0$，实际上对应新的，系数为1的同余方程：$x\equiv x_0 \pmod m$
## 中国剩余定理
由上一章扩展欧几里得，我们已经：
- 掌握求解单个一元线性同余方程的方法，
- 了解同余方程的解其实是另一个系数为1的模数相同的同余方程。
扩展到多个同余方程构成的方程组，若方程组内某式系数不为1，则可以先用Ext_GCD解该方程，得到系数为一的新方程替换原方程。
**中国剩余定理（孙子定理）**：
求解同余方程组：$\begin{cases}
x\equiv a_1 \pmod {m_1},\\
x\equiv a_2 \pmod {m_2},\\
\ \vdots\\
x\equiv a_n \pmod {m_n},\\
\end{cases}$，其中$m_i$互质
令$\begin{cases}
M=m_1m_2\cdots m_n\\
\displaystyle M_i=\frac{M}{m_i}\\
M_iM_i^{-1}\equiv 1\pmod {m_i}\\
\end{cases}$
则方程组的解为 $x_0 = \displaystyle\sum_{i=1}^na_iM_iM_i^{-1}\pmod M$
```cpp
ll china(vector<ll> a, vector<ll> m) {
ll M = 1L;
for (int i = 0; i < m.size(); i++) {
M *= m[i];
}
ll res = 0L;
for (int i = 0; i < m.size(); i++) {
res += (((a[i]%M) * (M / m[i]))%M) * inv(M / m[i], m[i]);
res %= M;
}
return res;
}
```
**模数不互质时的处理**：
- 对两个方程构成的方程组 $\begin{cases}x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\end{cases}$
- 转化为 $x=m_1p+a_1=m_2q+a_2$，$p,q\in\mathbb{Z}$，整理得不定方程 $m_1p-m_2q=a_2-a_1$
- 由裴蜀定理，有解当且仅当 $\gcd(m_1, m_2)|(a_2-a_1)$
- 由Ext_GCD得到一个解$(p_0,q_0)$
- 原先的方程组的解为：$x\equiv m_1p+a_1\pmod{\text{lcm}(m_1, m_2)}$
- 对于多个方程构成的方程组，两两合并即可。
![]()