一、公因数

1. 公因数的定义

下面提到一组整数的时候，如无特殊说明，要求数量 $n \ge 1$。

</aside>

【公因数的定义】对一组 $n$ 个整数（$n \ge 1$）$a_1, a_2, \cdots, a_n \in \Z$ 和 $d \in \Z, \, d \neq 0$，如果 $d \mid (a_1, a_2, \cdots, a_n)$，则称 $d$ 是这组整数的公因数 (Common Divisor/Factor)。
【公因数集合的定义】对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$，记公因数集合为：

$$ \begin{align*}

{\rm CD} (a_1, a_2, \cdots, a_n) &= \{ d \in \Z, \, d \neq 0 \mid (d \mid (a_1, a_2, \cdots, a_n)) \} \\

&= \{ d \in \Z, \, d \neq 0 \mid (\forall \, i \in [1, n] \cap \Z, \, d \mid a_i) \} \\

&= \{ d \in \Z, \, d \neq 0 \mid (\forall \, i \in [1, n] \cap \Z, \, \exists \, q_i \in \Z, \, a_i = q_i d) \} \\

\end{align*} $$
- 也就是对于 $d \in \Z, \, d \neq 0$，有 $d \mid (a_1, a_2, \cdots, a_n) \Leftrightarrow d \in {\rm CD} (a_1, a_2, \cdots, a_n)$。
**【公因数集合的等价表达】**对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$，公因数集合满足：

$$ \begin{align*}

{\rm CD} (a_1, a_2, \cdots, a_n) &= \bigcap_{i=1}^n \, {\rm Div} \, a_i \\

&= \bigcap_{i=1}^n \, \{ d \in \Z, \, d \neq 0 \, | \, (d \mid a_i) \} \\

\end{align*} $$

**证明：**作 $C_1 = \{ d \in \Z, \, d \neq 0 \mid (\forall \, i \in [1, n] \cap \Z, \, d \mid a_i) \}$ 和 $C_2 = \bigcap_{i=1}^n \, \{ d \in \Z, \, d \neq 0 \, | \, (d \mid a_i)$，仍然是考虑 $\subseteq$ 和 $\supseteq$，但我就不写了，写出来太废话了。

2. 公因数的基本性质

下面会用 ${\rm CD}$ 或 ${\rm CD}_a$ 这样的标记简写 ${\rm CD} (a_1, a_2, \cdots, a_n)$；GCD 等同理。

</aside>

**【公因数的存在性】**一组整数的公因数必定存在，比如一定有 $1 \in {\rm CD}$，这也就保证了 ${\rm CD} \neq \empty$。

**证：**因为 $\forall a \in \Z, \, 1 \mid a$，得到 $1 \mid (a_1, a_2, \cdots, a_n)$。
- 另外，因为下面要提到的公因数成对存在，$-1$ 也是公因数，因而也就是 $1, -1 \in {\rm CD}$。
**【公因数成对存在】**对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$，如果 $d \in {\rm CD}$，那么 $-d \in {\rm CD}$。

**证：**根据 $d \mid (a_1, a_2, \cdots, a_n)$ 得到 $-d \mid (a_1, a_2, \cdots, a_n)$。
**【公因数集合的大小和取值范围】**对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$：
1. 当 $a_1 = a_2 = \cdots = a_n =0$ 时，${\rm CD} = \Z \backslash \{0\}$，是无穷集。
  
  **证：**这时 $\forall \, i=1,2,\cdots,n$ 都有 $a_i =0$ 故都有 ${\rm Div} \, a_i \equiv \Z \backslash \{0\}$，因而 ${\rm CD} = \bigcap_{i=1}^n \, {\rm Div} \, a_i = \Z \backslash \{0\}$。
2. 否则即 $a_1, a_2, \cdots, a_n$ 不全为零，记非零索引集 $I_{\pm} = \{ i \in \{ 1, 2, \cdots, n \} \mid a_i \neq 0 \}$，这时可证明两个点：
  1. 如果 $d \in {\rm CD}$，那么 $|d| \le \min_{i \in I_{\pm}} |a_i|$。
  2. $|{\rm CD}| \le 2 \min_{i \in I_{\pm}}^n |a_i|$。
  证：
  1. 根据 $d \mid (a_1, a_2, \cdots, a_n)$，对于 $\forall i \in I_{\pm}$，有 $a_i \neq 0$，有 $|d| \le |a_i|$，因而得到 $|d| \le \min_{i \in I_{\pm}} |a_i|$，记 $l = \min_{i \in I_{\pm}} |a_i|$，知道必有 $l \ge 1$。
  2. 因为任何 $d \in {\rm CD}$ 都满足 $|d| \le l \Leftrightarrow -l \le d \le l$ 且 $d \in \Z, \, d \neq 0$，因而：
    
    $$ \begin{align*}
    
    {\rm CD} &\subseteq ([-l, l] \cap \Z ) \backslash \{0\} \\
    
    |{\rm CD}| &\le |([-l, l] \cap \Z ) \backslash \{0\}| = 2l
    
    \end{align*} $$
**【公因数的分解】**对于一组整数，如果 $d$ 是这组整数的公因数，且 $d=uv$（$u, v \in \Z$），那么 $u$ 和 $v$ 也是这组整数的公因数。
证：
- 因为 $d \mid (a_1, a_2, \cdots, a_n)$ 得到 $d \neq 0$，因而 $u, v \neq 0$。
- $\exists \, q_1, q_2, \cdots, q_n \in \Z$，有 $a_1=q_1d$，$a_2=q_2d$，……，$a_n=q_nd$，可以得到：
  - $a_1=q_1uv$，$a_2=q_2uv$，……，$a_n=q_nuv$。
- 那么当然 $u$ 和 $v$ 也是这组整数的公因数。
**【与 0 的公因数】**若 $b \in \Z$，$b \neq 0$，那么 ${\rm CD} (0, b) = {\rm Div} \,b$。

证：${\rm CD} (0, b) = {\rm Div} \,0 \cap {\rm Div} \,b = (\Z \backslash \{0\}) \cap {\rm Div} \,b = {\rm Div} \,b$。
**【公因数集合对数值的对称性】**对于一组整数 $a_1, a_2, \cdots, a_n \in \Z$，记录公因数集合为 ${\rm CD}$，那么：

$$ \forall k_1, k_2, \cdots, k_n \in \{ +1, -1 \}, \ {\rm CD}(k_1 a_1, k_2 a_2, \cdots, k_n a_n) = {\rm CD} $$
- 特别地，${\rm CD}(|a_1|, |a_2|, \cdots, |a_n|) = {\rm CD}$。
证：
- 考察 ${\rm CD} (k_1 a_1, k_2 a_2, \cdots, k_n a_n) = \bigcap_{i=1}^n \, {\rm Div} \, ( k_i a_i )$。根据因数集合的对称性知道 ${\rm Div} \, a_i = {\rm Div} \, (-a_i)$，因而 ${\rm Div} \, (k_ia_i) = {\rm Div} \, a_i$ 在 $k_i=\pm1$ 的时候均成立，因而 $\bigcap_{i=1}^n \, {\rm Div} \, ( k_i a_i ) = \bigcap_{i=1}^n \, {\rm Div} \, a_i = {\rm CD}$ 立明。
- 特别的，对于 $\forall i, |a_i|$，因为有
  
  $$ |a_i| = \begin{cases}
  
  1\cdot a_i, &a_i \ge 0 \\
  
  -1 \cdot a_i, &a_i < 0
  
  \end{cases} $$
  
  ，无论是什么情况，根据上面的性质 ${\rm CD}(|a_1|, |a_2|, \cdots, |a_n|) = {\rm CD}$ 都成立。

二、公倍数

1. 公倍数的定义

**【公倍数的定义】**对一组 $n$ 个非零整数（$n \ge 1$）$a_1, a_2, \cdots, a_n \in \Z \backslash \{ 0 \}$ 和 $s \in \Z$，如果 $(a_1, a_2, \cdots, a_n) \mid s$，则称 $s$ 是这组整数的公倍数 (Common Multiple)。
【公倍数集合的定义】对于一组非零整数 $a_1, a_2, \cdots, a_n \in \Z \backslash \{ 0 \}$，记公倍数集合为：

$$ \begin{align*}

{\rm CM} (a_1, a_2, \cdots, a_n) &= \{ s \in \Z \mid ((a_1, a_2, \cdots, a_n) \mid s) \} \\

&= \{ s \in \Z \mid (\forall \, i \in [1, n] \cap \Z, \, a_i \mid s) \} \\

&= \{ s \in \Z \mid (\forall \, i \in [1, n] \cap \Z, \, \exists \, q_i \in \Z, \, s = q_i a_i) \} \\

\end{align*} $$
- 也就是对于 $s \in \Z$，有 $(a_1, a_2, \cdots, a_n) \mid s \Leftrightarrow s \in {\rm CM} (a_1, a_2, \cdots, a_n)$。
- 正公倍数集合记为 ${\rm CM}_+ = \{ s \in {\rm CM} \mid s > 0 \}$。
**【公倍数集合的等价表达】**对于一组非零整数 $a_1, a_2, \cdots, a_n \in \Z \backslash \{ 0 \}$，公倍数集合满足：

$$ \begin{align*}

{\rm CM} (a_1, a_2, \cdots, a_n) &= \bigcap_{i=1}^n \, {\rm Mul} \, a_i \\

&= \bigcap_{i=1}^n \, \{ s \in \Z \, | \, (a_i \mid s) \} \\

&= \bigcap_{i=1}^n \, \{ qa_i \, | \, q \in \Z \} \\

\end{align*} $$

**证明：**略。