最近正好在搞同余，写一下。
同余
定义
-
设 \(m\in \mathbb{Z^+}\)，如果 \(a,b \in \mathbb Z\) 且 \(m \mid (a - b)\)，那么称 \(a\) 和 \(b\) 模 \(m\) 同余，记作 \(a \equiv b\pmod m\)；否则称 \(a\) 模 \(m\) 不同余于 \(b\)，记作 \(a \not \equiv b \pmod m\)。称 \(m\) 为同余的模。
-
由定理 2 可见，整数的集合被分成 \(m\) 个不同的集合，这些集合被称为模 \(m\) 剩余类（同余类），每个同余类中的任意两个整数都是模 \(m\) 同余的。
-
设 \(m\in \mathbb{Z^+}\)，给定整数 \(a\)，由带余除法有 \(a=b\times m+r\)，其中 \(0\le r< m\)，称 \(r\) 为 \(a\) 的模 \(m\) 最小非负剩余，是 \(a\) 模 \(m\) 的结果。如果 \(m\) 不整除 \(a\)，称 \(r\) 为 \(a\) 的模 \(m\) 最小正剩余。
-
另一个常用的记号是 \(a\bmod m = r\)，它表示 \(r\) 是 \(a\) 除以 \(m\) 的余数。
-
一个模 \(m\) 完全剩余系是一个整数的集合，使得每个整数恰和此集合中的一个元素模 \(m\) 同余。
注意，这个集合中可能会有负数。 -
由带余除法可知，集合 \(\{0,1,\ldots,m-1\}\) 是模 \(m\) 完全剩余系，称为模 \(m\) 最小非负剩余的集合。
定理与证明
- 定理 1
若 \(a,b\in \mathbb{Z}\)，如果 \(a\equiv b\pmod m\) 有且仅有一个整数 \(k\) 满足 \(a=b+k\times m\)。
- 证明 1
若 \(a\equiv b \pmod m\)，则 \(m \mid (a-b)\)，一定有一整数 \(k\) 满足 \(k\times m=a-b\)，变一下式： \(a = b+k\times m\)。
- 定理 2
设 \(m\in\mathbb{Z^+}\)，则模 \(m\) 的同余满足下面的性质。
-
对于 \(a\in \mathbb{Z}\)，\(a\equiv a\pmod m\)。
-
对于 \(a,b\in \mathbb{Z}\)，且 \(a\equiv b \pmod m\)，则 \(b\equiv a \pmod m\)。
-
对于 \(a,b,c\in\mathbb{Z}\)，且 \(a\equiv b\pmod m\) 和 \(b\equiv c \pmod m\)，则 \(a\equiv c \pmod m\)。
- 证明 2
-
因为 \(a - a=0\)，所以 \((m \mid (a-a))=(m\mid0)=(a\equiv a\pmod m)\)。
-
若 \(a\equiv b\pmod m\)，则根据定理 1，一定有 \(k\in \mathbb{Z}\)，使得 \(k\times m=a-b\)，左右同时乘上 \(-1\)，可得 \(-k\times m=b-a\)，说明 \(m \mid (b-a)\)，即 \(b\equiv a\pmod m\)。
-
若 \(a\equiv b\pmod m\)，且 \(b\equiv c\pmod m\)，则有 \(m\mid(a-b)\) 和 \(m\mid(b-c)\)。从而存在整数 \(k\) 和 \(l\)，使得 \(k\times m=a-b,l\times m=b-c\)。于是，\(a-c=(a-b)+(a-c)=k\times m+l\times m=(k+l)\times m\)。因此，\(m \mid (a-c)\)，\(a\equiv c\pmod m\)。