一、同余的定义与基本性质

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$ 当且仅当 $m \mid (a - b)$。

  证：

  • $\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$。

4. 运算保持同余

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

  **证：**通过充要条件证明。有 $m \mid (a_1 - a_2)$ 且 $m \mid (b_1 - b_2)$，作和即 $m \mid ((a_1 + b_1) - (a_2 + 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 a_2 \pmod m$ 且 $b_1 \equiv b_2 \pmod m$，那么两侧作积仍保持同余即 $a_1 b_1 \equiv a_2 b_2 \pmod m$。

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