合同.md

设$m$是任意非零整数，$m\mid a$，我们就说$a$合同于$0$模$m$，记为：

$$ a\equiv0(mod\ m) $$

一般来说，若$a-b$被$m$整除，则我们说$a$合同于$b$模$m$

$$ a\equiv b(mod\ m) $$

一个数被$m$整除，当且仅当此数被$-m$整除，所以若未指定$m$而一般地讨论模$m$合同时，我们总假定$m$是正整数

性质

1. $a\equiv b(mod\ m)$当且仅当$a,b$对$m$同余
2. $a\equiv a$
3. 若$a\equiv b$，则$b\equiv a$
4. 若$a\equiv b$，$b\equiv c$，则$a\equiv c$

第2到4条性质说明合同是一种等价关系，每一个等价类称为模$m$的一个剩余类

5. 若$a\equiv b(mod\ m)$，$c\equiv d(mod\ m)$，则$a\pm c\equiv b\pm d(mod\ m)$，$ac\equiv bd(mod\ m)$
6. 若$a\equiv b(mod\ m)$，则$a\pm k\equiv b\pm k(mod\ m)$，其中$k$为整数
7. 若$a+b\equiv c(mod\ m)$，则$a\equiv c-b(mod\ m)$
8. 若$a\equiv b(mod\ m)$，则$ac\equiv bc(mod\ m)$
9. 若$a\equiv b(mod\ m)$，则$a^n\equiv b^n(mod\ m)$
10. 若$c\ne 0$而$ac\equiv bc(mod\ mc)$，则$a\equiv b(mod\ m)$
11. 若$c$和$m$互质，则由$ac\equiv bc(mod\ m)$可以推出$a\equiv b(mod\ m)$
12. 若$ac\equiv bc(mod\ m)$，且$gcd(c,m)=d$，则$a\equiv b(mod\ m/d)$
13. 若$p$为质数，$c\not\equiv 0(mod\ p)$，而$ac\equiv bc(mod\ p)$，则$a\equiv b(mod\ p)$
14. 设$p(x)$是整系数多项式，$x$和$y$是整数变量，则由$x\equiv y(mod\ m)$可得$p(x)\equiv p(y)(mod\ m)$