算數基本定理

這裡我們又碰到一個典型的有關存在性與唯一性的問題. 這裡的存在性指的就是對一大於 1 的整數可以找到有限多個質數使其可以寫成這些質數的乘積, 而唯一性就是指的就是寫法唯一. 由於正整數和負整數的分解只差一個負號, 我們只需考慮正整數的情況.

Theorem 1.5.1 (The Fundamental Theorem of Arithmetic) 假設 a $\in$ $\mathbb {N}$ 且 a > 1, 則存在 p₁,..., p_r, 其中 p_i 是相異的質數, 滿足

a = p₁^{n₁ ...}p_r^n_r, n_i $\displaystyle \in$ $\displaystyle \mathbb {N}$ , $\displaystyle \forall$ i $\displaystyle \in$ {1,..., r}.

如果 a 可以分解成另外的形式 a = q₁^{m₁ ...}q_s^m_s, 其中 q_i 是相異的質數, 則 r = s 且經過變換順序可得 p_i = q_i, n_i = m_i, $\forall$ i $\in$ {1,..., r}.

証明. 我們分開來證存在性與唯一性.

首先來看存在性: 簡單來說存在性就是要證明每一個大於 1 的整數都可以寫成有限多個(可以相同)質數的乘積. 如果 a 本身是個質數, 則 a = p₁ (即 r = 1, n₁ = 1), 得證存在性. 如果 a 不是質數呢? 由定義知存在 a₁, b₁ $\in$ $\mathbb {N}$ 且 a₁ $\ne$ 1, b₁ $\ne$ 1 滿足 a = a₁^.b₁. 接下來就是看 a₁, b₁ 是不是質數了. 如果其中有一個不是質數, 我們就繼續分解下去直到得到質數為止. 這個過程一定會停下來因為每次分解後得的數越來越小. 當然最後就可以將 a 寫成一些質數的乘積了. 這樣的證明方式, 相信大家會有一種說不清楚的感覺, 所以我們還是用數學歸納法來證明. 當 a = 2 時由於 2 是質數, 所以在這情況存在性是對的. 接著假設對所有從 2 到 a - 1 的整數存在性是對的. 如果 a 是質數, 那存在性自然成立. 如果 a 不是質數, 則知 a = a₁^.b₁ 其中 a₁, b₁ $\in$ $\mathbb {N}$ 且 1 < a₁ < a 及 1 < b₁ < a. 故利用歸納假設知 a₁ 和 b₁ 都可寫成有限多個質數的乘積, 所以得證 a 也可以寫成有限多個質數的乘積.

我們依然用歸納法證唯一性, 假設

a = p₁^{n₁ ...}p_r^n_r = q₁^{m₁ ...}q_s^m_s,

其中 p₁,..., p_r 是兩兩相異的質數, 且 q₁,..., q_s 也是兩兩相異的質數. 由於 p₁ 是質數, 故由 p₁ | a = q₁^{m₁ ...}q_s^m_s 以及 Corollary 1.4.3 知存在某個 j $\in$ {1,..., s} 滿足 p₁ | q_j. 變換一下順序我們可以假設 p₁ | q₁. 由於 q₁ 是質數, q₁ 的因數只能是 ±1 或 ±q₁. 故由 p₁ | q₁ 知 p₁ = q₁. 現在考慮

$\displaystyle {\frac{a}{p_1}}$ = p₁^{n₁ - 1 ...}p_r^n_r = q₁^{m₁ - 1 ...}q_s^m_s.

由於 a/p₁ < a, 故利用唯一性的歸納法假設我們得 r = s 且 p₁ = q₁,..., p_r = q_r 以及 n₁ = m₁, n₂ = m₂,..., n_r = m_r, 故得證唯一性. $\qedsymbol$

一般來說我們將一正整數 a 寫成質數之乘積 a = p₁^{n₁ ...}p_r^n_r 時, 為了唯一性我們要求每個質數 p_i 的次方 n_i 都是正的, 也就是說我們只挑出 a 的質因數 p₁,..., p_r. 不過當要討論兩正數 a, b 時為了方便比較, 我們通常會挑出 a 和 b 所有的質因數再將 a, b 寫成這些質數之乘積的樣子. 也就是說可寫成 a = p₁^{n₁ ...}p_r^n_r 以及 b = p₁^{m₁ ...}p_r^m_r 其中對於 i $\in$ {1,..., r}, p_i| a 或 p_i| b, 且 n_i $\ge$ 0, m_i $\ge$ 0. 注意這裡由於 a 的質因數未必就是 b 的質因數, 反之亦然, 所以 n_i, m_i 有可能為 0. 這樣寫法的方便性就是我們不必區分哪些 p_i 是 a 的質因數, 哪些是 b 的質因數. 利用這樣的寫法我們很容易將 a, b 的最大公因數表示出來.

Proposition 1.5.2 假設 a, b $\in$ $\mathbb {N}$ 且 a, b > 1. 若 a = p₁^{n₁ ...}p_r^n₁ 且 b = p₁^{m₁ ...}p_r^m_r, 其中 p₁,..., p_r 為相異質數且 n_i, m_i $\ge$ 0, 則 a, b 的正公因數都可寫成 p₁^{t₁ ...}p_r^t_r 的形式, 其中 0 $\le$ t_i $\le$ min{n_i, m_i}. 特別地, 我們有

gcd(a, b) = p₁^{min{n₁, m₁} ...}p_r^{min{n_r, m_r}}.

証明. 首先回顧一下 min{x, y} 表示 x, y 中最小之數. 現假設 d 是 a, b 的正公因數, 則由 d| a 我們知若 p 是 d 的質因數, 則由 p| d 知 p| a. 故由 Corollary 1.4.3 知存在 i $\in$ {1,..., r} 使得 p| p_i. 因此由 p, p_i 皆為質數得 p = p_i. 也就是說 d 的質因數必在 {p₁,..., p_r} 中, 故 d 一定可以寫成 p₁^{t₁ ...}p_r^t_r 的形式, 其中 t_i $\ge$ 0. 又由於對任意 i $\in$ {1,..., r} 皆有 p_i^t_i| d 故 p_i^t_i| a, 亦即 p_i^t_i| p₁^{n₁ ...}p_r^n_r. 由於若 i $\ne$ j 則 p_i $\ne$ p_j, 知此時 gcd(p_i^t_i, p_j^n_j) = 1, 故由 1.2.7(1) 得 p_i^t_i| p_i^n_i, 也就是說 t_i $\le$ n_i. 同理由 d| b 可得 t_i $\le$ m_i, 故得證 0 $\le$ t_i $\le$ min{n_i, m_i}.

現令 d = p₁^{min{n₁, m₁} ...}p_r^{min{n_r, m_r}}, 馬上得知 d 為 a, b 之公因數. 又由上知任意 a, b 的公因數 d' 皆滿足 d'| d, 故知 d = gcd(a, b). $\qedsymbol$

雖然 Proposition 1.5.2 也是一個求得兩個數之最大公因數之方法, 不過在實際情況 (尤其是處理很大的數時) 由於分解質因數是很困難的事情, 所以仍是以輾轉相除法得最大公因數較管用. Proposition 1.5.2 重要之處是它很明確的告訴我們最大公因數長什麼樣子, 這在一些抽象理論的推導是有用的.

証明. 由於 ab = p₁^{n₁ + m₁ ...}p_r^{n_r + m_r} 利用 Proposition 1.2.8 以及 Proposition 1.5.2 知

lcm(a, b) = $\displaystyle {\frac{ab}{\gcd(a,b)}}$ = p₁^{n₁ + m₁ - min{n₁, m₁} ...}p_r^{n_r + m_r - min{n_r, m_r}}.

對任意二數 x, y, 不失一般性我們假設 x $\ge$ y, 此時我們有 min{x, y} = y 且 max{x, y} = x, 因此得 x + y = min{x, y} + max{x, y}. 所以對任意 i $\in$ {1,..., r} 我們皆有 max{n_i, m_i} = n_i + m_i - min{n_i, m_i}, 因此得證本定理. $\qedsymbol$

當我們有多於兩個的整數時, 我們就可以利用質因數分解以及 Proposition 1.2.12 和 Proposition 1.2.13 將他們的最大公因數和最小公倍數寫下. 例如若 a = p₁^{n₁ ...}p_r^n₁, b = p₁^{m₁ ...}p_r^m_r 且 c = p₁^{t₁ ...}p_r^t_r, 其中 p₁,..., p_r 為相異質數且 n_i, m_i, t_i $\ge$ 0, 則