『算法-ACM 竞赛-数学-数论』同余及其性质（超详细）

定义：
$给定一个正整数m，及两个整数a、b。\如果a-b被m整除，则称a与b模m同余，记作a≡b(mod m) \否则称a与b模m不同余，记作a≢ b(mod m)。$

性质：

1. $a,b模m同余\Leftrightarrow a=b+Km \quad k为任意整数$
2. 自反性：$a≡a（mod \quad m)$
   对称性：$a≡b（mod \quad m)\Leftrightarrow b≡a（mod \quad m)$
   传递性：$a≡b（mod \quad m)且 b≡c（mod \quad m)\Rightarrow a≡c (mod \quad m)$
3. $a≡b（mod\ m)且c≡d（mod\ m) \则 \①a+c=b+d（mod\ m)\②ac=bd（mod\ m)$
   结论：
   $a_i≡b_i（mod \quad m) (i=1,2,3…..,k)\则\
   ①\sum_{i=1}^{k}a_i\equiv \sum_{i=1}^{k}b_i(mod\ m)\ \
   \
   ②\prod_{i=1}^{k}a_i\equiv \prod_{i=1}^{k}b_i(mod\ m)$
   推论：
   $① a≡b（mod \quad m)\Rightarrow na≡nb (mod \quad m) 其中a为整数\② a≡b（mod \quad m)\Rightarrow a^n≡b^n (mod \quad m) 其中a为整数$
4. $ac≡bc（mod \quad m)且GCD(c,m)=1 \ \Rightarrow a≡b (mod \quad m)$
5. $a≡b（mod \quad m)\Rightarrow an≡bn (mod \quad mn) \ 其中n>0$
6. $a≡b（mod \quad m)且d|gcd(a,b,m)\Rightarrow a/d≡b/d (mod \quad m/d)$
7. $a≡b（mod \quad m)且d|m\Rightarrow a≡b（mod \quad d)$
8. $a≡b（mod \quad m_i) (i=1,2,3…..,k) \Leftrightarrow a≡b（mod \quad Lcm[m_1,m_2….m_k] (i=1,2,3…..,k)$
9. $a≡b（mod \quad m)\Rightarrow gcd(a,m)=gcd(b,m)$

敲公式不易，转走请附上链接，谢谢。