同余

同余是初等数论中的基本概念, 大致来说是模算术下的一种等价关系.

1定义

定义 1.1 (同余的整除定义). 设 $a, b, m$ 为整数, 若 $m$ 整除 $a - b$ , 则称 $a$ 与 $b$ 关于模 $m$ 同余. 记为 $a \equiv b (mod m) .$

定义 1.2 (同余的模算术定义). 设 $a, b, m$ 为整数, 若 $a mod m = b mod m$ , 则称 $a$ 与 $b$ 关于模 $m$ 同余. 记为 $a \equiv b (mod m) .$

•	任意两个整数关于模 $\pm 1$ 同余.

•	$r, m + r, 2 m + r, \dots, km + r$ 两两关于模 $m$ 同余, 其中 $k, r$ 为整数, $m$ 为非零整数.

如无特别说明, 本节 $a, b, c, d, k$ 均为整数, $m$ 为非零整数.

•	自反性: $a \equiv a (mod m)$ .

•	对称性: 若 $a \equiv b (mod m)$ , 则 $b \equiv a (mod m)$ .

•	传递性: 若 $a \equiv b (mod m)$ 且 $b \equiv c (mod m)$ , 则 $a \equiv c (mod m)$ .

若 $a \equiv b (mod m)$ , $c \equiv d (mod m)$ , 则有如下性质:

•	模意义下加减法: $a \pm b \equiv c \pm d (mod m)$ .

•	模意义下乘法: $ab \equiv c d (mod m)$ .