6590: 学习系列 —— 同余概述
[Creator : ]
Description
【定义】
同余给定正整数 $m$，若用 $m$ 去除两个整数 $a$ 和 $b$，所得的余数相同，称 $a$ 和 $b$ 对模 $m$ 同余，记作 $a \equiv b (\bmod m)$，并称该式为同余式，否则，称 $a$ 和 $b$ 对模 $m$ 不同余。
由与同余关系是等价关系，对于所有整数会被分为 $m$ 的集合，这些集合称为模 $m$ 剩余类（同余类）。每个集合中的任意两个数都是模 $m$ 同余的。
【定理】
$a \equiv b\ (\bmod m)$，当且仅当 $m|(a-b)$。
$a \equiv b\ (\bmod m)$，当且仅当存在正整数 $k$，使得 $a=b+km$。
同余关系是等价关系，即
(1）自反性：$a \equiv a\ (\bmod m)$
(2）对称性：$a \equiv b\ (\bmod m)$，则 $b \equiv a\ (\bmod m)$
(3）传递性：$a \equiv b\ (\bmod m),\ b \equiv c\ (\bmod m)$，则 $a \equiv c\ (\bmod m)$
若 $a,b,c,d$ 是整数，$m$ 是正整数，且 $a \equiv b\ (\bmod m),\ c \equiv d\ (\bmod m)$，则：
4. $a+b \equiv b+c\ (\bmod m)$
5. $a-b \equiv b-c\ (\bmod m)$
6. $ac \equiv bc\ (\bmod m)$
7. $ac \equiv bc\ (\bmod m),\ c \neq 0$，则 $a \equiv b\ (\bmod \frac{m}{\text{gcd}(m,c)})$
8. $ax+cy=bx+dy\ (\bmod m)$，其中 $x,y$ 为任意整数，即同余式可以相加
9. $ac \equiv bd\ (\bmod m)$，即同余式可以相乘
10. $a^n \equiv b^n,\ n>0$
11. $f(a) \equiv f(b)\ (\bmod m)$，其中 $f(x) 为任一整数多项式
定理：若 $a,b,c,d$ 为整数，$m$ 为正整数，则：
若 $a \equiv b\ (\bmod m)$，且 $d|m$，则 $a \equiv b\ (\bmod d)$
若$a \equiv b\ (\bmod m)$，则 $(a,m)=(b,m)$，其中 $(a,m)$ 为 $a$ 和 $m$ 的最大公约数
同余给定正整数 $m$，若用 $m$ 去除两个整数 $a$ 和 $b$，所得的余数相同，称 $a$ 和 $b$ 对模 $m$ 同余，记作 $a \equiv b (\bmod m)$，并称该式为同余式，否则，称 $a$ 和 $b$ 对模 $m$ 不同余。
由与同余关系是等价关系，对于所有整数会被分为 $m$ 的集合，这些集合称为模 $m$ 剩余类（同余类）。每个集合中的任意两个数都是模 $m$ 同余的。
【定理】
$a \equiv b\ (\bmod m)$，当且仅当 $m|(a-b)$。
$a \equiv b\ (\bmod m)$，当且仅当存在正整数 $k$，使得 $a=b+km$。
同余关系是等价关系，即
(1）自反性：$a \equiv a\ (\bmod m)$
(2）对称性：$a \equiv b\ (\bmod m)$，则 $b \equiv a\ (\bmod m)$
(3）传递性：$a \equiv b\ (\bmod m),\ b \equiv c\ (\bmod m)$，则 $a \equiv c\ (\bmod m)$
若 $a,b,c,d$ 是整数，$m$ 是正整数，且 $a \equiv b\ (\bmod m),\ c \equiv d\ (\bmod m)$，则：
4. $a+b \equiv b+c\ (\bmod m)$
5. $a-b \equiv b-c\ (\bmod m)$
6. $ac \equiv bc\ (\bmod m)$
7. $ac \equiv bc\ (\bmod m),\ c \neq 0$，则 $a \equiv b\ (\bmod \frac{m}{\text{gcd}(m,c)})$
8. $ax+cy=bx+dy\ (\bmod m)$，其中 $x,y$ 为任意整数，即同余式可以相加
9. $ac \equiv bd\ (\bmod m)$，即同余式可以相乘
10. $a^n \equiv b^n,\ n>0$
11. $f(a) \equiv f(b)\ (\bmod m)$，其中 $f(x) 为任一整数多项式
定理：若 $a,b,c,d$ 为整数，$m$ 为正整数，则：
若 $a \equiv b\ (\bmod m)$，且 $d|m$，则 $a \equiv b\ (\bmod d)$
若$a \equiv b\ (\bmod m)$，则 $(a,m)=(b,m)$，其中 $(a,m)$ 为 $a$ 和 $m$ 的最大公约数