算術基本定理
本文簡介初等數論中的算術基本定理，即每個正整數均具有唯一的質因數分解。
1 算術基本定理
1.1 連乘積
本文中，我們採用以下連乘積的定義： \[\begin{split} \prod_{i=m}^n a_i = \begin{cases} \rod{4}{0}1 & \when m > n \\ \displaystyle a_m \cdot \prod_{i=m+1}^n a_i & \when m \leq n \end{cases} \period \end{split}\]
1.2 算術基本定理
定理 1（算術基本定理）說明對每個正整數均能表示成質數的連乘積（稱為正整數的質因數分解），且這種表示法具有唯一性。例如 3600 可表示為 \[\begin{split}3600 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \period\end{split}\]
以下採用的定理 1（算術基本定理）的證明會使用到歐幾里得引理（可參見〈貝祖引理與歐幾里得引理〉中的定理 3）：對任意正整數 $a \jcomma b \comma$若 $ab$ 的一個正因數 $c$ 與 $a$ 互質，則 $c$ 必定整除 $b \period$
定理 1（算術基本定理） 任一正整數均對應唯一一組質因數分解。亦即，下列敘述成立：
- 對任意正整數 $n \comma$均存在非負整數 $k$ 與質數 $p_0 \cm p_1 \cm \ldots \cm p_{k-1}$ 使得 \[\begin{split}n = \prod_{i=0}^{k-1} p_i \period\end{split}\]
- 若 $k \jcomma \ell$ 為非負整數，且 $p_0 \cm p_1 \cm \ldots \cm p_{k-1} \cm q_0 \cm q_1 \cm \ldots \cm q_{\ell-1}$ 為滿足 \[\begin{split} \prod_{i=0}^{k-1} p_i = \prod_{i=0}^{\ell-1} q_i \end{split}\] 的質數，其中 $p_0 \leq p_1 \leq \cdots \leq p_{k-1}$ 且 $q_0 \leq q_1 \leq \cdots \leq q_{\ell-1} \comma$則我們有 $k = \ell \comma$且 $p_i = q_i$ 對所有 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\}$ 均成立。
證明 首先證明 (a)，我們對 $n$ 使用數學歸納法。由於 1 可表示為空積 $1 = \prod_{i=0}^{-1} p_i \comma$故 (a) 在 $n = 1$ 時成立。
接著我們假設 (a) 在 $n \leq m-1$ 時成立，其中 $m$ 為不小於 2 的正整數，我們說明 (a) 在 $n = m$ 時也成立。
狀況 1：$n$ 為質數。此時 $n$ 可表示為一個質數的乘積（即 $n = \prod_{i=0}^0 p_i \comma$其中 $p_0 = n \rparen \mkern-9mu \period$
狀況 2：$n$ 為合數，即存在 $r, s \in \{2 \cm 3 \cm \ldots \cm n \varminus 1\}$ 使得 $n = rs \period$由歸納假設可知存在非負整數 $k \jcomma \ell$ 與質數 $p_0 \cm p_1 \cm \ldots \cm p_{k-1} \cm p_k \cm p_{k+1} \cm \ldots \cm p_{k+\ell-1}$ 使得 \[\begin{split}r = \prod_{i=0}^{k-1} p_i \quad \text{與} \quad s = \prod_{i=k}^{k+\ell-1} p_i\end{split}\] 成立。此時我們有 \[\begin{split}n = rs = \prod_{i=0}^{k+\ell-1} p_i \comma\end{split}\] 故 (a) 得證。
接著證明 (b)，我們對 $k$ 使用數學歸納法。
當 $k = 0$ 時，由 \[\begin{split} 1 = \prod_{i=0}^{-1} p_i = \prod_{i=0}^{\ell-1} q_i \end{split}\] 可知 $\ell = 0 \comma$故 (b) 在 $k = 0$ 時成立。
接著我們假設 (b) 在 $k \leq m-1$ 時成立，其中 $m$ 為正整數，我們說明 (b) 在 $k = m$ 時也成立。假設 $p_0 \cm p_1 \cm \ldots \cm p_{k-1} \cm q_0 \cm q_1 \cm \ldots \cm q_{\ell-1}$ 為滿足 \[\begin{split} \prod_{i=0}^{k-1} p_i = \prod_{i=0}^{\ell-1} q_i \end{split}\] 的質數，其中 $p_0 \leq p_1 \leq \cdots \leq p_{k-1}$ 且 $q_0 \leq q_1 \leq \cdots \leq q_{\ell-1} \period$
我們先利用歸謬法證明 $p_{k-1} = q_{\ell-1} \period$假設 $p_{k-1} \neq q_{\ell-1} \period$
狀況 1：$p_{k-1} < q_{\ell-1} \period$此時由於對所有 $i \in \{0 \cm 1 \cm \ldots \cm k \varminus 1\} \comma$$p_i$ 均與 $q_{\ell-1}$ 互質，由歐幾里得引理會導出矛盾。
狀況 2：$p_{k-1} > q_{\ell-1} \period$此時由於對所有 $i \in \{0 \cm 1 \cm \ldots \cm \ell \varminus 1\} \comma$$q_i$ 均與 $p_{k-1}$ 互質，由歐幾里得引理會導出矛盾。
因而 $p_{k-1} = q_{\ell-1}$ 成立。此時由於 \[\begin{split} \prod_{i=0}^{k-2} p_i = \prod_{i=0}^{\ell-2} q_i \comma \end{split}\] 由歸納假設可知 $k - 1 = \ell - 1$ 成立，且有 \[\begin{split}(p_0 \cm p_1 \cm \ldots \cm p_{k-2}) = (q_0 \cm q_1 \cm \ldots \cm q_{\ell-2}) \comma\end{split}\] 故 (b) 得證。