模意义下及同余的公式整理

模意义下及同余的公式整理我们在做同余或模意义下式子的时候可以把元素都先处理到最简然后就基本可以用普通的算式性质了。最简的意思是若apapap把a←a mod pa\leftarrow a\bmod pa←amodp。模a mod ba−⌊ab⌋ba\bmod ba-\lfloor\frac{a}{b}\rfloor bamodba−⌊ba​⌋b(ab) mod p(a mod pb mod p) mod p(ab)\bmod p(a\bmod pb\bmod p)\bmod p(ab)modp(amodpbmodp)modp(a−b) mod p(a mod p−(b mod p)p) mod p(a-b)\bmod p(a\bmod p-(b\bmod p)p)\bmod p(a−b)modp(amodp−(bmodp)p)modpab mod pa mod p×b mod pab\bmod pa\bmod p\times b\bmod pabmodpamodp×bmodpkp mod p0kp\bmod p0kpmodp0若a0a0a0令a−kpba-kpba−kpb。其中kkk为非负的整数b0b0b0。其中kkk是满足−kp≥a-kp\ge a−kp≥a的最小整数值。则a≡b( mod p)a\equiv b(\bmod p)a≡b(modp)。若−pa0-pa0−pa0a≡p−a( mod p)a\equiv p-a(\bmod p)a≡p−a(modp)同余a≡a( mod p)a\equiv a(\bmod p)a≡a(modp)若a≡ba\equiv ba≡b则b≡ab\equiv ab≡a若a≡b,b≡ca\equiv b,b\equiv ca≡b,b≡c则a≡ca\equiv ca≡c若a≡ba\equiv ba≡b则a±c≡b±ca\pm c\equiv b\pm ca±c≡b±c若a≡b,c≡da\equiv b,c\equiv da≡b,c≡d则a±c≡b±da\pm c\equiv b\pm da±c≡b±d若a≡b( mod p)a\equiv b(\bmod p)a≡b(modp)则ac≡bc( mod p)ac\equiv bc(\bmod p)ac≡bc(modp)除法乘法逆元若xa≡1( mod p)xa\equiv 1(\bmod p)xa≡1(modp)则称a≡x−1( mod p)a\equiv x^{-1}(\bmod p)a≡x−1(modp)也称aaa为xxx在模ppp意义下的乘法逆元。怎么求就不用多说了一般情况下ppp为质数最小的axp−2ax^{p-2}axp−2。或者O(n)O(n)O(n)递推求逆元。所以模意义下的除法ab≡ab−1( mod p)\frac{a}{b}\equiv ab^{-1}(\bmod p)ba​≡ab−1(modp)。所以若ac≡bc( mod p)ac\equiv bc(\bmod p)ac≡bc(modp)未必有a≡b( mod p)a\equiv b(\bmod p)a≡b(modp)。