取模

定义

对于 a, b ∈ ℤ，满足 b > 0，则存在唯一的整数 q, r，满足 a = b × q + r (0 ≤ r < b)。

称 q 为商、r 为余数。余数用 a mod  b 表示，在 C++ 中表示为 a % b。

性质

  • (a + b) mod  m = (a mod  m + b mod  m) mod  m。

  • (a − b) mod  m = (a mod  m − b mod  m) mod  m。

    需要注意的是，a mod  m 可能小于 b mod  m，那么结果在 C++ 中计算的结果将是负数。

    但是在数学中，负数取模的结果仍然是非负数，故在 C++ 中一般将其写作 (a % m - b % m + m) % m。

  • (a × b) mod  m = (a mod  m × b mod  m) mod  m。

PS：注意，(a ÷ b) mod  m = ((a mod  m) ÷ (b mod  m)) mod  m 这个等式不一定成立！

反例：a = 12, b = 3, m = 6，(a ÷ b) mod  m = 4，而 0 ≠ 4，故上述等式不一定成立。

如果想在模意义下实现除法，请参见 乘法逆元。

同余

定义

若 x, y ∈ ℤ 除以 m 的余数相同，则称 x, y 模 m 同余，记为 x ≡ y (mod  m)。

性质

  • 反身性：x ≡ x (mod  m)。
  • 对称性：x ≡ y (mod  m)，则 y ≡ x (mod  m)。
  • 传递性：如果 x ≡ y (mod  m)，y ≡ z (mod  m)，则 x ≡ z (mod  m)。
  • 同加减性：如果 x ≡ y (mod  m)，则 x ± z ≡ y ± z (mod  m)。
  • 同乘性：如果 x ≡ y (mod  m)，则 x × z ≡ y × z (mod  m)。
  • 同幂性：如果 x ≡ y (mod  m)，则 xz ≡ yz (mod  m)。

此外，还有一个十分重要的性质： x ≡ y (mod  m) ⇔ m ∣ (x − y)