同余的定义与基本性质

1. 同余的定义

• **【同余的定义】**给定 $m \in \Z^+$，将其叫做「模数」，对 $a, b \in \Z$，作整数除法 $a = p_a m + r_a$ 和 $b = p_b m + r_b$（$r_a, r_b \in [0, m) \cap \Z$），如果 $r_a = r_b$，我们就说 $a, b$ 在模 $m$ 意义下同余，记为 $a \equiv b \pmod m$；否则称 $a, b$ 在模 $m$ 意义下不同余，记为 $a \not \equiv b \pmod m$。

2. 同余是等价关系

• **【同余是等价关系】**同余是一个 $\Z$ 上的等价关系。即 $\forall m \in \Z^+$，满足：
  • （自反）$\forall a \in \Z$，$a \equiv a \pmod m$。
  • （对称）$\forall a, b \in \Z$，如果 $a \equiv b \pmod m$，那么 $b \equiv a \pmod m$。
  • （传递）$\forall a, b, c \in \Z$，如果 $a \equiv b \pmod m$ 且 $b \equiv c \pmod m$，那么 $a \equiv c \pmod m$。

3. 同余的充分必要条件

• 【同余的充分必要条件】$\forall m \in \Z^+$，$\forall a, b \in \Z$，$a \equiv b \pmod m$ 当且仅当如下二者任一成立：

  1. $m \mid (a - b)$。
  2. $\exists k \in \Z$ 使得 $a - b = km$。

  证：

  1. 证明原条件 $\Leftrightarrow$「1.」。
     • $\Rightarrow$：记录 $a = p_a m + r_a$ 和 $b = p_b m + r_b$（$r_a, r_b \in [0, m) \cap \Z$）。根据条件有 $r_a = r_b$。因而 $a - b = m(p_a - p_b)$，因而 $m \mid (a - b)$。
     • $\Leftarrow$：记录 $a = p_a m + r_a$ 和 $b = p_b m + r_b$（$r_a, r_b \in [0, m) \cap \Z$），得到 $a - b = m (p_a - p_b) + (r_a - r_b)$。根据条件得到 $m \mid (m (p_a - p_b) + (r_a - r_b))$，显然 $m \mid m(p_a - p_b)$，作差得到 $m \mid (r_a - r_b)$。因而 $(r_a - r_b) = tm$（$t \in \Z$）。又 $r_a, r_b \in [0, m)$ 导出 $(r_a - r_b) \in (-m, m)$，因而 $t = 0$ 即 $r_a = r_b$。
  2. 证明「1.」$\Leftrightarrow$「2.」。根据整除的定义，$\Rightarrow$ 和 $\Leftarrow$ 都非常显然。

4. 保持同余的性质

• 【同余式的一侧加减模数的倍数仍保持同余】$\forall m \in \Z^+$，$\forall a, b \in \Z$，$a \equiv b \pmod m$ ，那么任取 $k \in \Z$ 有 $(a+km) \equiv b \pmod m$ 和 $a \equiv (b+km) \pmod m$。

  **证：**通过充要条件证明。有 $m \mid (a-b)$，显然 $m \mid km$ ，因而作和得到 $m \mid ((a+km)-b)$，作差得到 $m \mid (a-(b+km))$。

  • 能很快地导出：同余式的一侧换为其对模数 $m$ 求余的结果仍保持同余。比如作整数除法 $a = p_a m + r_a$ 就有余数 $r_a = a - p_a m$ 是原数减去 $-p_a$ 倍模数得到的，那么 $r_a \equiv b \pmod m$ 仍成立。

• 【两同余式作和仍保持同余】$\forall m \in \Z^+$，$\forall a_1, b_1, a_2, b_2 \in \Z$，如果 $a_1 \equiv b_1 \pmod m$ 且 $a_2 \equiv b_2 \pmod m$，那么两侧作和仍保持同余即 $a_1 + a_2 \equiv b_1 + b_2 \pmod m$。

  **证：**通过充要条件证明。有 $m \mid (a_1 - b_1)$ 且 $m \mid (a_2 - b_2)$，作和即 $m \mid ((a_1 + a_2) - (b_1 + b_2))$。

• 【同余式移项仍保持同余】$\forall m \in \Z^+$，$\forall a, b, c \in \Z$，如果 $a + b \equiv c \pmod m$，那么 $a \equiv c - b \pmod m$。

  **证：**通过充要条件证明。有 $m \mid ((a + b) - c)$ 即 $m \mid (a - (c - b))$。

• 【两同余式作积仍保持同余】$\forall m \in \Z^+$，$\forall a_1, b_1, a_2, b_2 \in \Z$，如果 $a_1 \equiv b_1 \pmod m$ 且 $a_2 \equiv b_2 \pmod m$，那么两侧作积仍保持同余即 $a_1 a_2 \equiv b_1 b_2 \pmod m$。

  **证：**通过充要条件证明。有 $m \mid (a_1 - b_1)$ 且 $m \mid (a_2 - b_2)$，即 $a_1 = b_1 + pm$ 且 $a_2 = b_2 + qm$（$p, q \in \Z$）。那么 $a_1 a_2 = b_1 b_2 + m(qb_1 + pb_2 + pqm)$ 即 $m \mid (a_1a_2 - b_1b_2)$。

• 【同余式两侧同数乘仍保持同余】$\forall m \in \Z^+$，$\forall a, b \in \Z$，如果 $a \equiv b \pmod m$，那么 $\forall k \in \Z$，$ka \equiv kb \pmod m$。

  **证：**对 $k$ 自反后作积即得。

• 【两个多项式如果系数同余则恒同余】若对 $i = 0, 1, \dots, n$ 都有 $a_i \equiv b_i \pmod m$，那么 $\forall x \in \Z$ 都有：

  $$ a_n x^n + a_{n-1}x^{n-1} + \cdots + a_0 \equiv b_n x^n + b_{n-1}x^{n-1} + \cdots + b_0 \pmod m $$

  **证：**对 $x^n, x^{n-1}, \dots, 1$ 使用自反，逐项作积后加和。

• 【数除仍保持同余】$\forall m \in \Z^+$，$\forall a, b, a_1, b_1, d \in \Z$，如果 $a \equiv b \pmod m$，且 $a = a_1d$、$b = b_1d$，且 $d \perp m$（注意这个条件），那么 $a_1 \equiv b_1 \pmod m$。

  证：通过充要条件证明。有 $m \mid (a -b )$ 即 $m \mid d(a_1 - b_1)$，加上 $d \perp m$ 导出 $m \mid (a_1 - b_1)$。

5. 变换模数的保持同余

• 【数乘，但带上模数】$\forall m \in \Z^+$，$\forall a, b \in \Z$，如果 $a \equiv b \pmod m$，那么 $\forall k \in \Z^+$，$ka \equiv kb \pmod {km}$。

  证：通过充要条件证明。有 $m \mid (a -b )$，两侧同乘 $k$ 得到 $km \mid (ka - kb)$。

• 【数除，但带上模数】$\forall m \in \Z^+$，$\forall a, b, a_1, b_1, m_1 \in \Z$ 且 $d \in \Z^+$，如果 $a \equiv b \pmod m$，且 $a = a_1d$、$b = b_1d$、$m = m_1 d$，那么 $a_1 \equiv b_1 \pmod {m_1}$。

  证：通过充要条件证明。有 $m \mid (a -b )$ 即 $m_1d \mid (a_1 - b_1)d$，因数倍数一起缩小得到 $m_1 \mid (a_1 - b_1)$。并从 $m, d \in \Z^+$ 得到 $m_1 \in \Z^+$ 是一个合法模数。

• 【LCM 模数变化】$\forall m_1, m_2, \dots, m_k \in \Z^+$，$\forall a, b \in \Z$，如果 $\forall i = 1, 2, \dots, k$ 都有 $a \equiv b \pmod {m_i}$，那么作 $M = {\rm LCM} (m_1, m_2, \dots, m_k)$，有 $a \equiv b \pmod M$。

  证：通过充要条件证明。有 $(m_1, m_2, \cdots, m_k) \mid (a -b )$，因而 $(a-b) \in {\rm CM}(m_1, m_2, \cdots, m_k)$ 。根据 LCM 的性质得到 $M \mid (a-b)$。$M \in \Z^+$ 显然是一个合法模数。