当 x \bmod \ m = y \bmod \ m 时，我们说 x 和 y 关于 m 同余，表示为 x \equiv y \pmod m。
3. 同余定理：
定理 1：当 a \equiv b \pmod m 且 d \mid m 时，有 a \equiv b \pmod d
定理 2：当 a \equiv b \pmod m 且 c \equiv d \pmod m 时，有
a + c \equiv b + d \pmod m
\\
a - c \equiv b - d \pmod m
\\
a \times b \equiv c \times d \pmod m
定理 3：当 ac \equiv bd \pmod m 且 \gcd(c,m) = 1 时，有 a \equiv b \pmod m
定理 4：当 a \equiv b \pmod m 时，对于任意的 c \ne 0，有 ac \equiv bc \pmod m
定理 5：当 a \equiv b \pmod m 时，对于任意的 k > 0，有 a ^ k \equiv b ^ k \pmod m
定理 6：当 a \equiv b \pmod m 时,对于任意的整数 t，有 a = b + tm
4. 证明：
定理 1：
\because a \equiv b \pmod m
\\
\therefore \text{设 } qm + r = a,pm + r = b
\\
\because d \mid m
\\
\therefore \text{设 } d = km
\\
\therefore a = qkd + r,b = pkd + r
\\
\therefore a \bmod \ d = r,b \bmod \ d =r
\\
\therefore a \equiv b \pmod d
定理 2：
\because a \equiv b \pmod m,c \equiv d \pmod m
\\
\therefore \text{设} a = km + r,b = tm + r,c = pm + w,d = qm + w
\\
(1)\therefore a + c = km + pm + r + w,b + d = tm + qm + r + w
\\
\therefore (a + c) \bmod m = (r + w) \bmod m,(b + d) \bmod m= (r + w) \bmod m
\\
\therefore (a + c) \equiv (b + d) \pmod m
\\
(2)\therefore a - c = km - pm + r - w,b - d = tm - qm +r -w
\\
(a - b) \bmod m = (r - w) \bmod m,(b - d) \bmod m = (r - w) \bmod m
\\
\therefore (a - c) \equiv (b - d) \pmod m
\\
(3)\therefore a * c = kpm^2 + prm + kwm + rw,b * d = tqm^2 + qrm + twm + rw
\\
(ab) \bmod m = (rw) \bmod m,(bd) \bmod m = (rw) \bmod m
\\
\therefore (a * c) \equiv (b * d) \pmod m
定理 3:
\because ac \equiv bc \pmod m
\\
\therefore m \mid (a-b) \text{或} (a - b) \mid m
\\
\because gcd(m,c) = 1
\\
\therefore m \text{是} (a - b) \text{的因数或倍数}
\\
\therefore a \bmod m = b \bmod m
\\
\therefore a \equiv b \pmod m
定理 4:
\because a \equiv b \pmod m
\\
\therefore m \mid (a - b)
\\
\therefore mc \mid (a - b)c
\\
\therefore ac \bmod m = bc \bmod m
\\
\therefore ac \equiv bc \pmod mc
定理 5:
\because a \equiv b \pmod m
\\
\therefore a \cdot a = b \cdot b \pmod m
\\
\therefore a^k = b^k \pmod m
定理 6：
\because a \equiv b \pmod m
\\
\therefore \text{设} a = pm + r,b = qm + r
\\
\therefore \text{令} k = p - q
\\
\therefore pm + r = gm + r + km
\\
\therefore a = b + km