同余定理
同余定理是数论中的重要概念。给定一个正整数 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)。
同余性质
- 反身性：a ≡ a(mod m)
- 对称性： 若 a ≡ b(mod m)，则 b ≡ a(mod m)
- 传递性： 若 a ≡ b(mod m)，b ≡ c(mod m)，则 a ≡ c(mod m)
- 同余式相加：若 a ≡ b(mod m)，b ≡ c(mod m)，则 a ± c ≡ b ± d(mod m)
- 同余式相乘：若a ≡ b(mod m)，b ≡ c(mod m)，则 ac ≡ bd(mod m)
- 线性运算：如果 a ≡ b(mod m)，c ≡ d(mod m)，那么 a ± c ≡ b ± d(mod m)，且 a * c ≡ b * d(mod m)
- 除法：若 ac ≡ bc (mod m) c ≠ 0 则 a ≡ b (mod m/gcd(c, m))
其中 gcd(c, m) 表示 c, m 的最大公约数。特殊地 , gcd(c, m)=1 则 a ≡ b (mod m) - 幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)
- 若a ≡ b (mod m)，n | m,则 a ≡ b (mod n)
- 若a ≡ b (mod mi) (i = 1,2…n) 则 a ≡ b (mod [m1,m2,…mn])
其中[m1,m2,…mn] 表示m1,m2,…mn的最小公倍数
相关定理
- 欧拉定理
- 费马小定理
- 中国剩余定理（孙子定理）
