同余公式和性质

╰+攻爆jí腚メ 2022-08-04 13:48 142阅读 0赞

基本性质：

（1）若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)

（2）(a % p)=(b % p)意味a≡b (% p)

（3）对称性：a≡b (% p)等价于b≡a (% p)

（4）传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)

运算规则：

模运算与基本四则运算有些相似，但是除法例外。其规则如下：  
(a + b) % p = (a % p + b % p) % p （1）  
(a - b) % p = (a % p - b % p) % p （2）  
(a \* b) % p = (a % p \* b % p) % p （3）  
ab % p = ((a % p)b) % p （4）

结合率： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

((a\*b) % p \* c)% p = (a \* (b\*c) % p) % p （6）

交换率： (a + b) % p = (b+a) % p （7）

(a \* b) % p = (b \* a) % p （8）

分配率： ((a +b)% p \* c) % p = ((a \* c) % p + (b \* c) % p) % p （9）

重要定理：若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）

若a≡b (% p)，则对于任意的c，都有(a \* c) ≡ (b \* c) (%p)；（11）

若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

(a \* c) ≡ (b \* d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

若a≡b (% p)，则对于任意的c，都有ac≡ bc (%p)； （13）

第二组性质：

1.如果 ![a /equiv b /pmod\{m\}][a _equiv b _pmod_m]，那么 *m* | (*a* − *b*) ，这里 *m* | (*a* − *b*) 表示 (*a* − *b*) 能被 *m* 整除

2.如果 ![a /equiv b /pmod\{m\}][a _equiv b _pmod_m]，![b /equiv c /pmod\{m\}][b _equiv c _pmod_m], 那么![a /equiv c /pmod\{m\}][a _equiv c _pmod_m]

3.如果 ![a /equiv b /pmod\{m\}][a _equiv b _pmod_m]，![c /equiv d/pmod\{m\}][c _equiv d_pmod_m], 那么![a+c /equiv b+d /pmod\{m\}][a_c _equiv b_d _pmod_m]，![a-c /equiv b-d /pmod\{m\}][a-c _equiv b-d _pmod_m]，![ac /equiv bd /pmod\{m\}][ac _equiv bd _pmod_m]，![a/c /equiv b /d /pmod\{m\}][a_c _equiv b _d _pmod_m]

4如果 ![a /equiv b /pmod\{m\}][a _equiv b _pmod_m]， 那么 ![a^n /equiv b^n /pmod\{m\}][a_n _equiv b_n _pmod_m]

5. 如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m）

[a _equiv b _pmod_m]: /images/20220731/7323eca4800d445fb5a3739e0ab9fc0f.png
[b _equiv c _pmod_m]: http://upload.wikimedia.org/math/7/2/c/72c4fa0bd69956b7e68d3d8cc2ec9d5c.png
[a _equiv c _pmod_m]: /images/20220731/294a270da80843c8b04ee60d0de68fc0.png
[c _equiv d_pmod_m]: http://upload.wikimedia.org/math/7/7/b/77b3768cf453ddc62ff2c3e668b93fad.png
[a_c _equiv b_d _pmod_m]: http://upload.wikimedia.org/math/5/8/7/5870db21ef07cf004708ae0a08c86699.png
[a-c _equiv b-d _pmod_m]: http://upload.wikimedia.org/math/9/e/f/9ef96c57e3ad5d862af3178c718177d6.png
[ac _equiv bd _pmod_m]: http://upload.wikimedia.org/math/3/9/0/390116f8d52af94ccdb17c5ad2e199c0.png
[a_c _equiv b _d _pmod_m]: /images/20220731/c5d4446d60334023aff0dcfb282cf8b9.png
[a_n _equiv b_n _pmod_m]: /images/20220731/e6aea628aa5a49b18a7270c3bf139d2c.png