整除
若 \(a / b (b \ne 0)\) 为整数，则称 \(b\) 整除 \(a\) ，记作 \(b \mid a\) 。若 \(a / b\) 和 \(c / b\) 的余数相等，则称 \(a, c\) 模 \(b\) 同余。
同余
关于同余，有以下命题等价：
- \(a\) 和 \(b\) 是模 \(d\) 同余的。
- 存在某个整数 \(n\) ，使 \(a = b + nd\) 。
- \(d\) 整除 \(a - b\) 。
由此可以轻易推出以下性质：
同余的基本性质
- \[a \equiv b \pmod p \text{且} c \equiv d \pmod p \Rightarrow a \pm c \equiv b \pm d \]
- \[a \equiv b \pmod p \Rightarrow ak \equiv bk \pmod {pk} \]
- \[k\mid p \text{且} a \equiv b \pmod p \Rightarrow a \equiv b \pmod k \]
- \[\text{有逆元时两侧可同除} \]
模运算基本性质
- \[(a + b) \bmod p = ((a \bmod p) + (b \bmod p)) \bmod p \]
- \[ab \bmod p = (a \bmod p)(b \bmod p) \bmod p \]
- \[a \bmod kb \bmod b = a \bmod b \]
欧几里得辗转相除法(gcd)
给定整数 \(a, b\) ，将它们的最大公因数记作 \(\gcd(a, b)\) ，欧几里得辗转相除法便是用来求 \(\gcd(a, b)\) 的，因而简称 \(\gcd\) 。
记 \(a, b\) 的公因数集合为 \(T\) ，\(b , a \bmod b\) 的公因数集合为 \(T'\) ，有 \(T = T'\) 。证明：
设 \(u \subseteq T\) ，\(a = xu, b = yu\) ，$$a \bmod b = a - b \left \lfloor a / b \right \rfloor = xu - yu(\left \lfloor a / b \right \rfloor) = u[x - y(\left \lfloor a / b \right \rfloor)]$$ ，所以 \(u \mid a \bmod b\) 。因而 \(T \subseteq T'\) 。
同样的，记 \(v \subseteq T'\) ，\(b = nv, a \bmod b = mv\) ，$$a = a \bmod b + b \left \lfloor a / b \right \rfloor = mv + nv(\left \lfloor a / b \right \rfloor) = v[m + n\left \lfloor a / b \right \rfloor]$$ ，所以 \(v \mid a\) 。因而 \(T' \subseteq T\)。
综上， \(\gcd(a, b) = \gcd(b, a \bmod b)\) ，因而可以直接递归求解。时间复杂度为 \(\log(n)\) 。
边界：当 \(b = 0\) 时，\(\gcd(a, b) = a\) 。
code:
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
扩展欧几里得(exgcd)
由欧几里得辗转相除法，我们可以运用这个算法在求最大公因数的同时求出满足 $$ax + by = \gcd(a, b)$$ 的正整数解 \(x, y\) 。
对于边界条件 \(b = 0\) ， \(x = 1, y = 0\) 就是一组合法解（当然，此处 \(y\) 可以取任意数）。那么，设 \(a' = b, b' = a \bmod b\) ，且我们已经求出 \(x_0, y_0\) 满足 \(a'x_0 + b'y_0 = \gcd(a', b')\) ，于是：
\[\begin{aligned} \gcd(a, b) &= \gcd(a', b') \\ &= a'x_0 + b'y_0 \\ &= bx_0 + (a\bmod b)y_0 \\ &= bx_0 + (a - b \left \lfloor a / b \right \rfloor)y_0 \\ &= ay_0 + b(x_0 - \left \lfloor a / b \right \rfloor y_0) \end{aligned} \]因此，满足 \(ax + by = \gcd(a, b)\) 的 \(x = y_0, y = x_0 - \left \lfloor a / b \right \rfloor y_0\) 。
code:
int exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return a;
}
int a1 = exgcd(b, a % b, x, y);
int x1 = y, y1 = x - a / b * y;
x = x1, y = y1;
return a1;
}
乘法逆元
对于一个数 \(a\) ，若 \(ab = 1\) ，那么我们称 \(a\) 的逆元为 \(b\) ，记作 \(a^{-1}\) 。在同余中，则是若 \(ab \equiv 1\) , 则 \(b\) 为 \(a\) 的逆元。通常，我们通过找到 \(a\) 的逆元来避免除法。给定 \(a\) 和 \(b\) ，我们需要求出 \(x\) 满足 \(ax \equiv 1 \pmod b\) 。
逆元唯一性定理：逆元若存在，则总是唯一的。
反证法。设有 \(x \not \equiv y\) 使得 \(ax \equiv ay \equiv 1\) ，则有 \(axy \equiv ax(y) \equiv y\) ,且 \(axy \equiv ay(x) \equiv x\) , 则 \(x \equiv y\) ，矛盾。
逆元存在性定理：在模 \(m\) 下，当且仅当 \(a \bot m\) 时，\(a\) 的逆元存在。后续补充证明。
事实上， \(ax \equiv 1 \pmod b\) 等价于 \(ax + by = \gcd(a, b)\) 。由逆元存在性定理，\(a \bot b\) 时， \(ax + by = 1\) 。所以 \(ax = 1 - by\) ， \(ax \equiv 1\) 。而若 \(ax \equiv 1 \pmod b\) ，则 \(ax - 1 \equiv 0 \pmod b\) ，所以令 \(y = \frac{ax - 1}{b}\) , 就有 \(ax + by = 1\) 。因此这两者等价。我们就可以直接使用exgcd求出 \(a\) 在模 \(b\) 下的乘法逆元。不过有一个需要注意的是，使用exgcd求出来的逆元可能是负数，输出 (x % b + b) % b 就好啦！
裴蜀定理
不定方程 \(ax + by = c\) 有整数解 \(x, y\) 的充要条件是 \(\gcd(a, b) \mid c\) 。
证明：
当 \(\gcd(a, b) \mid c\) 时，我们可以先用exgcd求出\(ax +by = \gcd(a, b)\) 的解，然后同时乘以 \(\ c / gcd(a, b)\) 即可得出解。
当 \(\gcd(a, b) \not \mid c\) 时，在该方程两边同时除以 \(\gcd(a, b)\) ，发现方程左边为整数，右边为分数，则必定无解。
由此，我们就可以运用裴蜀定理直接证明逆元存在性定理了。
标签：gcd,数论,bmod,笔记,学习,int,逆元,ax,equiv From： https://www.cnblogs.com/yduck/p/17799163.html