2024.4.29 【锦水汤汤，与君长诀！】
Monday 三月二十一
数论专题
同余
除法定理
对于任何整数a,和正整数m，存在唯一整数q，r，使得满足\(0\le r < m,a = qm+r\)
其中$$q = \lfloor \frac{a}{m}\rfloor$$
为商，\(r = a \ mod \ m\)为余数
余数
将a mod m记作余数
同余
如果\(a \mod\ m = b \mod\ m\)，那么称a,b在模m意义下同余，记作
\[a \equiv b \pmod m \]且有\((a,m) = (b,m)\)
若\(d|m\),有\(a \equiv b \pmod d\)
同余是 等价关系，即同余具有
自反性：\(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\)。
设 \(f(x)=\sum_{i=0}^n a_ix^i\) 和
\(g(x)=\sum_{i=0}^n b_ix^i\) 是两个整系数多项式，\(m\in\mathbf{N}^*\)，则对任意整数 x 均有 \(f(x)\equiv g(x)\pmod m\)。进而若 \(a_i\equiv b_i\pmod m,~0\leq i\leq n\)，那么若 \(s\equiv t\pmod m\)，则 \(f(s)\equiv g(t)\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\) 成立时，有 \((a,m)=(b,m)\)。若 d 能整除 m 及 a,b 中的一个，则 d 必定能整除 a,b 中的另一个。
剩余系
剩余系是指模正整数
标签：2024.4,gcd,int,29,varphi,pmod,逆元,equiv From： https://www.cnblogs.com/white-ice/p/18166621