同余

两个整数除以同一个数 n 的余数相同，我们就说它们在这个 n 的世界里是 “一路人”

例如：两个整数 a，b 除以 m 的余数相同，就说它们模 m 同余，记作

1
a ≡ b (mod m)

整除性定义

根据带余除法，我们可将 a 和 b 分别表示为

1
2
3
a = q1 * m + r1 (0 ≤ r1 < m)

b = q2 * m + r2 (0 ≤ r2 < m)

因为余数相同，所以 r1 = r2（参考上一节的带余除法）

此时，我们将两式相减

1
2
3
a - b = (q1 * m + r1) - (q2 * m + r2)
      = (q1 - q2) * m
      = k * m

由于 q1, q2 均为整数，其差 k = q1 - q2 显然也是整数。因此 a - b 是 m 的整数倍

根据整除的定义，这说明 m 可以整除 a - b，即

1
m | (a - b)

代数表示法定义

已知 m | (a - b)

根据整除的数学定义：”若 x | y，则存在整数 k 使得 y = kx“

直接将 m 和 a - b 代入定义，立即得到

1
a - b = km

等价类

模 m 的所有整数可以分成 m 类

1
[0],[1],[2],…,[m−1]

例如模 5 时，它们除以 5 的余数都是 2

1
[2]={…, −8, −3, 2, 7, 12, 17, …}

实战案例

我们生活在一个只有 7 天的星期循环里（相当于模 7 的世界）

在这里，”今天（第 3 天）” 和 “过 7 天（第 10 天）”、”过 14 天（第 17 天）” 本质上是完全等价的，它们都属于 “星期三” 这同一天