You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
[原文链接](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)$ ；
|
|
|
|
|
|
|
