一、最大公因数 (GCD)

1. GCD 的定义

• **【最大公因数 (GCD) 的定义】**对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$（$n \ge 1$），最大公因数 (Greatest Common Divisor) 记为：

  $$ {\rm GCD}(a_1, a_2, \cdots, a_n) = \max {\rm CD}(a_1, a_2, \cdots, a_n) $$

  <aside> <img src="/icons/warning_gray.svg" alt="/icons/warning_gray.svg" width="40px" />

  有的书将 GCD 简记为 $(a_1, a_2, \cdots, a_n)$，不过我这里用 $(a_1, a_2, \cdots, a_n)$ 指代整数组，请留意区别。

  </aside>

  <aside> <img src="/icons/cards_gray.svg" alt="/icons/cards_gray.svg" width="40px" />

  需要引入一系列关于整数集上最大元的定义和性质（最小元类似）。将陆续以知识卡片的形式给出。

  • **【最大元的定义】**考察任意整数集的子集 $A \subseteq \Z$。如果存在这样的元素 $a^*$，满足：

    1. $a^* \in A$；
    2. $\forall \, a \in A, \, a \le a^*$。

    那么称 $a^*$ 是 $A$ 的最大元。

  • **【最大元的唯一性】*考察任意整数集的子集 $A \subseteq \Z$。如果 $a_1^$ 和 $a^_2$ 都是 $A$ 的最大元，那么一定有 $a_1^ = a_2^*$。

    证：根据最大元的定义可以导出 $a_2^* \le a_1^$ 和 $a_1^ \le a_2^$。因而 $a_1^ = a_2^*$。

    因而最大元可以被记为 $a^* = \max A$。

  </aside>

• **【GCD 的等价表达】*GCD 有三个证明用的常用等价表达：对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$ 和这组数的一个公因数 $d^ \in {\rm CD}$，$d^*$ 是这组数的 GCD 当且仅当满足如下三种情况中任一：

  1. $\forall \, d \in {\rm CD}$ 都有 $d \le d^*$。
  2. $\forall \, k > d^*$（$k \in \Z$）都有 $k \notin {\rm CD}$。
  3. $\forall \, d \in {\rm CD}$ 都有 $d \mid d^$，且 $d^ \ge 0$。

  <aside> <img src="/icons/cards_gray.svg" alt="/icons/cards_gray.svg" width="40px" />

  **【最大元的充要条件】考察任意整数集的子集 $A \subseteq \Z$。对于 $a^ \in A$，有 $a^ = \max A$ 等且仅当：$\forall \, b > a^*$（$b \in \Z$）都有 $b \notin A$。

  证：

  • $\Rightarrow$：假设 $\exists \, b^* > a^, \, b^ \in \Z$ 且有 $b^* \in A$，这也就是在说 $\exists \, b^* \in A, \, b^* > a^*$，与最大元的定义发生了矛盾。
  • $\Leftarrow$：假设 $a^$ 不是 $A$ 的最大元，那么 $\exists \, \hat a \in A , \, \hat a > a^$，这也就是在说 $\exists \, \hat a > a^*$（$\hat a \in \Z$）使得 $\hat a \in A$。与条件发生了矛盾。 </aside>

  **证：**第一种情况根据最大元的定义就能得证；第二种情况通过最大元的充要条件就能得证。下面证第三种情况，只需证第一种情况是第三种情况的充要条件。

  • $\Leftarrow$：显然成立，对于任意 $d \in {\rm CD}$，因为 $d \mid d^$ 马上得到 $d \le |d^| = d^*$。
  • $\Rightarrow$：首先由于公因数成对存在，知道 $d^* \ge 0$。
    • 对于任意 $d \in {\rm CD}$，根据下面会说的数目推广的裴蜀定理，有 $\forall \, k_1, k_2, \cdots, k_n \in \Z, \, d \mid \sum_{i=1}^n k_ia_i$，而根据条件知道 $d^$ 是 GCD，有 $\exists \, \tilde k_1, \tilde k_2, \cdots, \tilde k_n \in \Z, \, d^ = \sum_{i=1}^n \tilde k_ia_i$，结合可知 $d \mid d^*$。

2. GCD 的基本性质

• **【GCD 的存在性和上下界】**对于一组整数：

  1. 如果它们全为零，GCD 不存在。
  2. 如果它们不全为零，GCD 必定存在，且 GCD 一组上下界是 $[1, l]$ （这里 $l = \min_{i \in I_{\pm}} |a_i|$、$I_{\pm} = \{ i \in \{ 1, 2, \cdots, n \} \mid a_i \neq 0 \}$）。

  <aside> <img src="/icons/cards_gray.svg" alt="/icons/cards_gray.svg" width="40px" />

  【最大元存在的充要条件】

  • 考察任意整数集的子集 $A \subseteq \Z$。如果存在 $m \in \Z$ 使得 $\forall \, a \in A, \, a \le m$，那么称 $m$ 为 $A$ 的一个上界。
  • 设 $A \neq \emptyset$，那么 $A$ 存在最大元的充要条件是 $A$ 存在某个上界。
    • 且如果存在某上界时，最大元一定小于等于这个上界。

  证：

  • $\Rightarrow$：$A$ 的最大元显然就是 $A$ 的一个上界。
  • $\Leftarrow$（使用良序原理）：
    • 设 $m \in \Z$ 是 $A$ 的一个上界，构造集合 $S = \{ m-a \mid a \in A \}$。
    • 可以知道 $\forall \, s \in S$ 都 $\exists \, a \in A$ 使得 $s = m - a$。由于 $m$ 上界的定义有 $a \le m$，那么 $s \ge 0$。因而 $S \subseteq \N$。根据良序原理（自然数集的非空子集一定存在最小元素），记 $S$ 的最小元为 $s^*$。
    • 根据 $\forall \, s^* \in S$ ，$\exists \, a^* \in A$ 使得 $s^* = m - a^$。$\forall \, a \in A$ 有：$m-a \in S$，根据最小元性质有 $m-a \ge m-a^$ 即 $a^* \ge a$。因而 $a^*$ 是 $A$ 的最大元。
    • 根据 $s^* = m - a^* \ge 0$ 得到 $a^* \le m$，即最大元小于等于上界。 </aside>

  证：

  1. 如果全是零，${\rm CD} = \Z \backslash \{0\}$，最大元即 GCD 不存在。
  2. 如果不全是零：
     • 根据前面的证明有 ${\rm CD} \subseteq ([-l, l] \cap \Z ) \backslash \{0\}$ 和 $1 \in {\rm CD}$。
     • 据此，${\rm CD}$ 的最大元 GCD 小于等于上界 $l$ 且大于等于元素 $1$。

• **【平凡的 GCD】**当序列只有一个非零数 $a$（这时 $n=1$）时，${\rm GCD} (a) = |a|$。

  **证：**因为 ${\rm GCD} (a) \mid a$ 有 ${\rm GCD} (a) \le |a|$。又 $a \mid a \Rightarrow(|a|) \mid a$ 知道 $|a| \in {\rm Div} \, a = {\rm CD} (a)$ 因而 ${\rm GCD} (a) \ge |a|$，因而 ${\rm GCD} (a) = |a|$。

• 【与 0 的 GCD】

  • 若 $b \in \Z$，$b > 0$，那么 ${\rm GCD} (0, b) = b$。

    **证：**先前已证 ${\rm CD} (0, b) = {\rm Div} \,b$，而 $\forall \, d \in {\rm Div} \,b$ 都有 $d \le |b|=b$ 且 $b \in {\rm Div} \, b$，故 ${\rm Div} \,b$ 即 ${\rm CD} (0, b)$ 的最大元是 $b$，即 ${\rm GCD} (0, b) = b$。、

  • 若 $b \in \Z$，$b \neq 0$，那么 ${\rm GCD} (0, b) = |b|$。

    证：

    • 若 $b>0$，根据上定理有 ${\rm GCD} (0, b) = b =|b|$。
    • 若 $b < 0$，根据上定理有 ${\rm GCD} (0, -b) = -b$。根据 ${\rm Div} \, b = {\rm Div} (-b)$（因数集合对称性）可得 ${\rm CD} (0, b) = {\rm Div} \,0 \cap {\rm Div} \,b = {\rm Div} \,0 \cap {\rm Div} (-b) = {\rm CD} (0, -b)$，再得 ${\rm GCD} (0, b) = \max {\rm CD} (0, b) = \max {\rm CD} (0, -b) = {\rm GCD} (0, -b)$；联立得 ${\rm GCD} (0, b) = -b = |b|$。

• **【GCD 的增删定理】**对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$，如果 GCD 存在，记为 $d^*$：

  1. 如果为整数组中任意添加一个数（称增加的数为 $a_{n+1}$），那么添加后整数组 GCD 仍存在，记为 $d^+$，一定有：① $d^+ \le d^$；② $d^+ = {\rm GCD} (d^, a_{n+1})$。
  2. 如果从整数组中任意扣掉一个数（称被扣掉的数为 $a_k$，扣掉后组大小至少为 1），且删减后整数组 GCD 仍存在，记为 $d^-$，一定有 $d^- \ge d^*$。

  <aside> <img src="/icons/cards_gray.svg" alt="/icons/cards_gray.svg" width="40px" />

  **【最大元与包含关系】**考察任意整数集的子集 $A, B \subseteq \Z$，且有 $A \subseteq B$，且 $A, B$ 均存在最大元。那么：$\max A \le \max B$。

  证：

  • 记 $a^=\max A$、$b^ = \max B$。$\forall \, b \in B, \, b \le b^$，因而 $a^ \in A \subseteq B$ 即有 $a^* \in B$ 故 $a^* \le b^*$。 </aside>

  证：

  • 证明「1.」① 和「2.」：考察 ${\rm CD} = \bigcap_{i=1}^n \, {\rm Div} \, a_i$。记增删后的公因数集合分别为 ${\rm CD}^+$、${\rm CD}^-$，根据交集关系有 ${\rm CD} = {\rm CD}^- \cap {\rm Div} \, a_k$ 和 ${\rm CD}^+ = {\rm CD} \cap {\rm Div} \, a_{n+1}$，因而 ${\rm CD}^+ \subseteq {\rm CD}\subseteq {\rm CD}^-$。根据性质，最大元有关系 $d^+ \le d^* \le d^-$。
  • 证明「1.」②：记录 $D = {\rm CD}\{ d^*, a_{n+1} \}$，下面证明 $D={\rm CD^+}$。
    • $\subseteq$：对于任意 $d \in D$ 可知 $d \mid d^$ 以及 $d \mid a_{n+1}$，前者根据传递性有 $\forall i \in [1, n], \, d \mid d^ \mid a_i$，联立上后者就是 $d \mid (a_1, a_2, \cdots, a_n, a_{n+1})$，因而 $d \in {\rm CD^+}$。
    • $\supseteq$：对于任意 $d \in {\rm CD^+}$ 可知 $\forall i \in [1, n], \, d \mid a_i$ 以及 $d \mid a_{n+1}$。前者可以推出 $d \in {\rm CD}$，根据【GCD 的等价表达】「3.」有 $d \mid d^*$。；联立上后者即有 $d \in D$。

• **【对于一对有整除关系的数，最大公因数取因数的绝对值】**对于整数 $a, b \in \Z$（$a \neq 0$），如果有 $a \mid b$，那么 ${\rm GCD} (a, b) = |a|$。

  证：

  • 因为 ${\rm GCD} (a, b) \mid a$，因而 ${\rm GCD} (a, b) \le |a|$。
  • 因为 $a \mid b \Rightarrow (|a|) \mid b$，又 $a \mid a \Rightarrow (|a|) \mid a$ 恒成立，故 $|a| \in {\rm CD} (a, b)$。故 ${\rm GCD}(a, b) \ge |a|$。
  • 因而 ${\rm GCD} (a, b) = |a|$。

• **【为序列加入某数的倍数，最大公因数不变】**对于不全为零的数 $a_1, a_2, \cdots, a_n$，如果 $\exists i, \, a_i \mid b$，那么 ${\rm GCD} (a_1, a_2, \cdots, a_n, b) = {\rm GCD} (a_1, a_2, \cdots, a_n)$。

  • 特别地当 $n=1$，定理为 $a \mid b$ $\Rightarrow$ ${\rm GCD}(a, b) = {\rm GCD}(a) = |a|$ 与上面定理一致。

  **证：**记录 $d^+ = {\rm GCD} (a_1, a_2, \cdots, a_n, b)$，$d = {\rm GCD} (a_1, a_2, \cdots, a_n)$，根据 GCD 增删性质有 $d^+ = {\rm GCD} (d, b)$。因为 $\exists i$ 有 $d \mid a_i \mid b$ 因而 $d \mid b$。根据上面的定理，$d^+ = {\rm GCD} (d, b) = |d| = d$。

• **【最大公因数对数值的对称性】*记 $d^ = {\rm GCD}(a_1, a_2, \cdots, a_n)$，那么：

  $$ \forall k_1, k_2, \cdots, k_n \in \{ +1, -1 \}, \ {\rm GCD}(k_1 a_1, k_2 a_2, \cdots, k_n a_n) = d^* $$

  • 特别地，${\rm GCD}(|a_1|, |a_2|, \cdots, |a_n|) = d^*$。

  **证：**根据 ${\rm CD}(k_1 a_1, k_2 a_2, \cdots, k_n a_n) = {\rm CD}(a_1, a_2, \cdots, a_n)$，最大值肯定也相同。

• **【一组数的公因数集合与他们的最大公因数的因数集合相同】记 $d^ = {\rm GCD}(a_1, a_2, \cdots, a_n)$，那么 ${\rm Div} \, d^ = {\rm CD} (a_1, a_2, \cdots, a_n)$。

  证：

  • $\subseteq$：对于任意 $d \in {\rm Div} \, d^$，有 $d \neq 0$ 且 $d \mid d^$。由于 $d^* \in {\rm CD}$，$\forall i \in [1, n] \cup \Z$ 都有 $d^* \mid a_i$，根据整除的传递性有 $d \mid a_i$，因而 $d \in {\rm CD}$。
  • $\supseteq$：对于任意 $d \in {\rm CD}$，根据【GCD 的等价表达】「3.」，都有 $d \mid d^$ 成立，因而 $d \in {\rm Div} \, d^$。

3. 裴蜀定理

• **【裴蜀定理 (Bézout's lemma)】**对于 $a, b \in \Z$ 且 $a, b$ 不全为 0，记 ${\rm GCD}(a, b) = d^*$，有：
• **【裴蜀定理的数目推广】**对于一组不全为零的整数 $a_1, a_2, \cdots, a_n$，记 ${\rm GCD} = d^*$，有：

4. GCD 分解定理

• **【GCD 分解定理】**上一定理如果想要避免产生分数，可以用这个替代定理：对于两个非零整数 $a, b \in \Z \backslash \{ 0 \}$ 和一个正整数 $d>0$，${\rm GCD} (a, b) = d$ $\Leftrightarrow$ 存在唯一的一对互质整数 $p, q$ 使得 $a = dp, \, b=dq$。

5. GCD 的其他定理