python/TangDou/Topic/数论准备知识.md

[原文链接](https://blog.csdn.net/Sherry_Yue/article/details/88593730)

### 1. 同余符号：$\equiv$

**（1）含义**
两个整数$a，b$，若它们除以整数$m$所得的余数相等，则称$a，b$对于模$m$同余，记作$a≡b(mod \ m)$。读作$a$同余于$b$模$m$，或读作$a$与$b$关于模$m$同余。
例：$26≡14(mod \ 12)$。

**（2）定义**
设$m$是大于$1$的正整数，$a，b$是整数，如果$m|(a-b)$，则称$a$与$b$关于模$m$同余，记作$a≡b(mod \ m)$，读作$a$同余于$b$模$m$。

**（3）性质**
(1) 若$a≡0(mod\ m)$，则$m|a$;
(2) $a≡b(mod\ m)$等价于$a$与$b$分别用$m$去除，余数相同

### 2. 同余定理
（1）定义
给定一个正整数$m$，如果两个整数$a$和$b$满足$a-b$能够被$m$整除，即$(a-b)/m$得到一个整数，那么就称整数$a$与$b$对模$m$同余，记作$a≡b(mod\ m)$。



反身性：$a≡a (mod\ m)$；

对称性：若$a≡b(mod \ m)$，则$b≡a (mod\ m)$；

传递性：若$a≡b(mod \ m)$，$b≡c(mod \ m)$，则$a≡c(mod \ m)$；

同余式相加减：若$a≡b(mod\ m)$，$c≡d(mod \ m)$，则$a±c≡b±d(mod\ m)$；

同余式相乘：若$a≡b(mod\ m)，c≡d(mod\ m)$，则$a∗c≡b∗d(mod \ m)$。

同余式数乘：若$a≡b(mod\ m)$，则$a\times k≡b \times k(mod \ m)$，$k$为任意整数。


**除法**：若 $a∗c≡b∗c\ (mod\ m)$,$c≠0$，则 
$a≡b(mod\ m/(gcd(c,m)))$ ，其中$gcd(c,m)$表示$c$和$m$的最大公约数，特殊地，$gcd(c,m)=1$，则 $a≡b(mod \ m)$ ；


**幂运算**：如果$a≡b(mod \ m)$ ，那么 $a^n ≡b^n
 (mod \ m)$ ；