同余定理

同余定理是数论中的重要概念。给定一个正整数 m，如果两个整数 a 和 b 满足 (a - b) 能够被 m 整除，那么就称整数 a 与 b 对模 m 同余，记作 a ≡ b (mod m)。

简单的理解：
整数 a、b，被一个整数 m 相除时，得到相同的余数，那么称 a、b 关于 m 同余。
因为 a、b 同余所以当他们相减时，余数就抵消掉了，剩下的那部分就是能被 m 整除的。

【定义】 设 m 是大于 1 的正整数，a、b 是整数，如果 m | (a - b)，则称 a 与 b 关于模 m 同余，记作 a ≡ b (mod m)。

若 a ≡ 0 (mod m)，则 m | a;
a ≡ b (mod m) 等价于 a 与 b 分别用 m 去除，余数相同。
证明
充分性：
若 a 和 b 用 m 相除留下相同的余数 r，则 a = q1 m + r, b = q2 m + r, q1 和 q2 为某两个整数，由此的 a - b = (q1 m + r) - (q2 m - r) = m (q1 - q2)，根据整除定义，有 m | (a - b)，由同余式定义得出结论：a ≡ b (mod m)

必要性：
若 a 和 b 用 m 相除留下相同的余数r，则 a = q1m + r, b = q2 m + r, 所以 a - b = m (q1 - q2) 故 m | (a - b)。

同余性质

1. 反身性：a ≡ a(mod m)