模意义下及同余的公式整理
我们在做同余或模意义下式子的时候，可以把元素都先处理到最简，然后就基本可以用普通的算式性质了。
最简的意思是若 \(a>p\)，把 \(a\leftarrow a\bmod p\)。
模
- \(a\bmod b=a-\lfloor\frac{a}{b}\rfloor b\)
- \((a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)
- \((a-b)\bmod p=(a\bmod p-(b\bmod p)+p)\bmod p\)
- \(ab\bmod p=a\bmod p\times b\bmod p\)
- \(kp\bmod p=0\)
若 \(a<0\)：
令 \(a=-kp+b\)。其中 \(k\) 为非负的整数，\(b<0\)。
其中 \(k\) 是满足 \(-kp\ge a\) 的最小整数值。
则 \(a\equiv b(\bmod p)\)。
- 若 \(-p<a<0\)，\(a\equiv p-a(\bmod p)\)
同余
- \(a\equiv a(\bmod p)\)
- 若 \(a\equiv b\)，则 \(b\equiv a\)
- 若 \(a\equiv b,b\equiv c\)，则 \(a\equiv c\)
- 若 \(a\equiv b\)，则 \(a\pm c\equiv b\pm c\)
- 若 \(a\equiv b,c\equiv d\)，则 \(a\pm c\equiv b\pm d\)
- 若 \(a\equiv b(\bmod p)\)，则 \(ac\equiv bc(\bmod p)\)
除法（乘法逆元）：
若 \(xa\equiv 1(\bmod p)\)，则称 \(a\equiv x^{-1}(\bmod p)\)，也称 \(a\) 为 \(x\) 在模 \(p\) 意义下的乘法逆元。
怎么求就不用多说了，一般情况下 \(p\) 为质数，最小的 \(a=x^{p-2}\)。
或者 \(O(n)\) 递推求逆元。
所以模意义下的除法 \(\frac{a}{b}\equiv ab^{-1}(\bmod p)\)。
- 所以若 \(ac\equiv bc(\bmod p)\)，未必有 \(a\equiv b(\bmod p)\)。