除法原理

整數中最基本的定理應該就是整數的除法原理 Division Algorithm, 幾乎所有整數的基本性質都是由它推導出來.

Theorem 1.2.1 (Division Algorithm)   給定一正整數 n, 對任意的 m $\in$ $\mathbb {Z}$, 皆存在 h, r $\in$ $\mathbb {Z}$, 其中 0$\le$r < n, 滿足 m = h ^. n + r.

這是一個很重要的性質, 重要到我們以 Theorem 來稱呼它. 這個定理我們習慣稱為除法原理, 如此稱它當然就包含``除''這個概念. 不過因為我們現在僅談加(減)法和乘法的性質, 我們避免用除的概念.

証 明. 給定 n $\in$ $\mathbb {N}$ 且 m $\in$ $\mathbb {Z}$. 首先考慮 W = {m - t ^. n | t $\in$ $\mathbb {Z}$} 這一個集合. 也就是收集 m, m - n, m - 2n,... 以及 m + n, m + 2n,... 等元素所得集合. 因為 t 可取任何整數, 很容易就看出 W 一定包含一些非負的整數. 換言之, 若考慮 W' 為 W 中非負的元素所成的集合, 則 W' 是一個非空的整數的子集合. 故由整數的 well-ordering principle 知 W' 中存在最小的整數 r. 即 r 是 W 中最小的非負的整數. 因為 r $\in$ W, 由定義知存在 h $\in$ $\mathbb {Z}$ 滿足 r = m - h ^. n. 我們最主要的目的就是要證明 0$\le$r < n.

假設 r 不合我們的條件, 也就是說 r$\ge$n (別忘了 r 是非負整數的假設). 若如此, 我們可將 r 寫成 r = n + r', 其中 r'$\ge$ 0. 因此利用

m = h ^. n + r = h ^. n + (n + r') = (h + 1) ^. n + r',

我們得到 r' = m - (h + 1) ^. n $\in$ W. 但 0$\le$r' < r, 這和 r 是 W 中最小的非負整數相矛盾. 故得證本定理. $\qedsymbol$

要注意 Theorem 1.2.1 的證明我們用到整數上可以排序的 well-ordering principle, 因此雖然證明很簡單, 但並不能直接套用到其他的數系.

接下來我們就要利用除法原理來探討公因數及最大公因數的基本性質. 由於 a 和 - a 的因數是一樣的, 所以不失一般性, 在討論因數時我們僅討論正整數的情形. 我們就從兩個正整數的情形開始討論.

Proposition 1.2.2   假設 a, b $\in$ $\mathbb {N}$ 且 d 是 a 和 b 的公因數. 若 d' 是 a/d 和 b/d 的公因數, 則 dd' 是 a 和 b 的公因數.

証 明. 首先注意, 由於 d 是 a, b 的公因數, 故存在 m, n $\in$ $\mathbb {Z}$ 使得 a = dm 且 b = dn. 也就是說 a/d = m 和 b/d = n 皆為整數. 又 d' 是 m, n 的公因數故存在 m', n' $\in$ $\mathbb {Z}$ 使得 m = d'm' 且 n = d'n'. 整理得 a = dd'm' 且 b = dd'n' 故知 dd' 是 a 和 b 的公因數. $\qedsymbol$

若 Proposition 1.2.2 中我們取 d = gcd(a, b), 則利用最大公因數的定義我們可得以下之性質.

Corollary 1.2.3   假設 a, b $\in$ $\mathbb {N}$ 且 d = gcd(a, b). 則 a/d 和 b/d 互質.

証 明. 要證明 a/d 和 b/d 互質就是證 gcd(a/d, b/d )= 1. 然而要說明 gcd(a/d, b/d )= 1 就得說明若 d' 是 a/d 和 b/d 的一個正的公因數, 則 d' = 1. 事實上若 d' 是 a/d 和 b/d 的一個的公因數, 則由 Proposition 1.2.2 知 dd' 是 a, b 的公因數. 然而已知 d 是 a, b 公因數中最大的, 故知 d$\ge$dd'. 也就是說 d'$\le$1. 因此結合當初假設 d' 是 a, b 的一個正的公因數 (即 d'$\ge$1) 得證 d' = 1. $\qedsymbol$

一般要證明 d = gcd(a, b) 我們要證明兩件事. 首先要證明 d 是 a, b 的公因數, 再來就是證明 d 是 a 和 b 的公因數中最大的. 前面 Corollary 1.2.3 中我們要證明 gcd(a/d, b/d )= 1. 由於 1 必為 a/d, b/d 的公因數, 所以只要證明任意 a/d 和 b/d 的公因數皆小於等於 1 就可. 接著我們來看另一個最大公因數的性質順便在證明中學習證明最大公因數的方法.

Proposition 1.2.4   假設 a, b $\in$ $\mathbb {N}$, 令 d 為集合 S = {ma + nb | m, n $\in$ $\mathbb {Z}$} 中最小的正整數. 則 gcd(a, b) = d.

証 明. 首先注意由於這裡 m, n 是任意的整數, 所以我們知道集合 S = {ma + nb | m, n $\in$ $\mathbb {Z}$} 中必存在正整數. 所以 S 中的正整數必形成一個非空的子集合, 因此我們套用 well-ordering principle 知 S 中必有最小的正整數. 也就是說敘述中的 d 一定存在. 接著我們要按照前面提的兩個步驟證明 d 為 a, b 的最大公因數.

首先檢查 d| a 且 d| b. 依定義存在 m, n $\in$ $\mathbb {Z}$ 使得 d = ma + nb. 要檢查是否 d| a 直覺的方法就是將 a 除以 d 看看是否餘數為 0. 利用除法原理我們知存在 h, r $\in$ $\mathbb {Z}$ 使得 a = dh + r, 其中 0$\le$r < d. 因此有

r = a - dh = a - (ma + nb)h = (1 - mh)a - (nh)b.

由於 1 - mh 和 - nh 皆為整數依定義知 r $\in$ S. 今若 r$\ne$ 0 會導致 r 是 S 中小於 d 的一個正整數. 這和當初假設 d 是 S 中最小的正整數相矛盾, 故知 r = 0. 也就是說 d| a. 同理可證 d| b.

接著我們要證明 d 是 a, b 的公因數中最大的數. 也就是要證明若 d' 是 a, b 的公因數, 則 d'$\le$d. 今由於 d'| a 且 d'| b 由 Corollary 1.1.2 知 d'| ma + nb. 即 d'| d, 也就是說存在 l $\in$ $\mathbb {Z}$ 使得 d = d'l. 因此由已知 d > 0 當然得 d'$\le$d. $\qedsymbol$

在上面證明 d 除以 a 的餘數為 0 的過程中. 我們無法直接證明餘數為 0, 不過發現若餘數不為 0 的話會導致矛盾的結果, 因而確知其餘數非為 0 不可. 這樣證明的方法就是所謂的 ``反證法". 這樣的證明方法我們以後還會經常看到.

或許大家會奇怪, 一般來說找 a, b 的最大公因數只要在 a, b 有限多個公因數中找最大的就好了為什麼要自討苦吃在 {ma + nb | m, n $\in$ $\mathbb {Z}$} 這個有無窮多個元素的集合中找? 沒有錯如果 a, b 很具體的知道是什麼當然直接找, 然而當我們要討論一般的情形 a, b 是任何可能的整數不能用幾個具體例子代一代就了事. 所以雖然 Proposition 1.2.4 在實際操作時並不實用但要用到理論的推演時他卻是很好用來表達最大公因數的工具. 直接利用 Proposition 1.2.4 我們馬上有以下之性質.

Corollary 1.2.5   假設 a, b $\in$ $\mathbb {N}$ 且 d = gcd(a, b) 則存在 m, n $\in$ $\mathbb {Z}$ 使得 d = ma + nb. 而且對任意 d' $\in$ $\mathbb {Z}$, d' 是 a, b 的公因數若且唯若 d'| d.

証 明. 由 Proposition 1.2.4 我們知 d 在集合 S = {ma + nb | m, n $\in$ $\mathbb {Z}$} 中, 故依定義存在 m, n $\in$ $\mathbb {Z}$ 使得 d = ma + nb.

注意這裡``若且唯若"的意思就是說如果 d' 是 a, b 的公因數那麼 d 必整除 a, b 的最大公因數 d, 反之若 d' 整除 a, b 的最大公因數, 那麼 d' 一定是 a, b 的公因數. 由 Proposition 1.2.4 的證明我們知若 d' 是 a, b 的公因數則 d'| d. 反之若 d'| d, 則由於 d| a 且 d| b, 利用 Proposition 1.1.3(3) 知 d'| a 且 d'| b. 即 d' 為 a, b 的公因數. $\qedsymbol$

一般來說有的性質可以從甲可推得乙, 但這並不表示從乙可推得甲. 如果兩個性質可以互推, 我們就用``若且唯若"表示之. 特別要注意 Corollary 1.2.5 並不是說若有一個正整數 d 可找到 m, n $\in$ $\mathbb {Z}$ 使得 d = ma + nb, 則 d 就是 a, b 的公因數. 這是一開始大家在學習邏輯推論時常犯的錯誤. 其實 d 可以寫成 ma + nb 僅表示 d 會在集合 S = {ma + nb | m, n $\in$ $\mathbb {Z}$} 中, 並不表示 d 會是 S 中最小的正整數. 所以當然 d 就未必是 a, b 的最大公因數. 因此當你要證明 d 是 a, b 的最大公因數時, 還是得按部就班如前面所提的兩步驟進行, 千萬不要找到兩個整數 m, n 使得 d = ma + nb 就說 d 就是 a, b 的最大公因數. 當然了如果你要證明 a, b 互質 (即 gcd(a, b) = 1) 時可以利用找到 m, n 使得 ma + nb = 1 來處理. 這是因為此時 1 在 S 中, 故當然是 S 中最小的正整數了. 因此我們將此特殊情況列出.

Corollary 1.2.6   假設 a, b $\in$ $\mathbb {N}$. 則 gcd(a, b) = 1 若且唯若存在 m, n $\in$ $\mathbb {Z}$ 使得 ma + nb = 1.

証 明. 再強調一次, 要證明若且唯若必需兩個方向都證明.

若 gcd(a, b) = 1, 由 Corollary 1.2.5 知存在 m, n $\in$ $\mathbb {Z}$ 使得 1 = ma + nb. 反之, 若存在 m, n $\in$ $\mathbb {Z}$ 使得 ma + nb = 1, 則 1 必為集合 {ma + nb | m, n $\in$ $\mathbb {Z}$} 中最小的正整數, 故由 Proposition 1.2.4 知 gcd(a, b) = 1. $\qedsymbol$

以上的性質並沒有告訴我們怎麼找到 m, n 使得 ma + nb = gcd(a, b), 我們將會在下節介紹完輾轉相除法後給一個方法來求 m, n. 雖然目前我們不知如何求得 m, n, 不過從下一個探討 a, b 互質時的重要的性質我們可以看到僅僅知道它們的存在性在理論的推演就很管用了.

Proposition 1.2.7   假設 a, b $\in$ $\mathbb {N}$ 且 gcd(a, b) = 1. 我們有以下的性質:

1. 若 k $\in$ $\mathbb {Z}$ 且 a| bk, 則 a| k.
2. 若 l $\in$ $\mathbb {Z}$ 且 a| l 及 b| l, 則 ab| l.

証 明. 因為 gcd(a, b) = 1, 由 Corollary 1.2.6 我們知存在 m, n $\in$ $\mathbb {Z}$ 使得 ma + nb = 1.

(1) 將 ma + nb = 1 等式兩邊乘上 k 可得 mak + nbk = k. 然而假設 a| bk 故利用 a| ak 以及 Corollary 1.1.2 知 a| k.

(2) 由 a| l 以及 b| l 知存在 r, s $\in$ $\mathbb {Z}$ 使得 l = ar = bs. 因為 a| ar 故得 a| bs. 再由 gcd(a, b) = 1 的假設利用 (1) 可得 a| s. 換言之存在 t $\in$ $\mathbb {Z}$ 使得 s = at. 將之帶回 l = bs 得 l = bat, 得證 ab| l. $\qedsymbol$

要注意 Proposition 1.2.7 的條件. 一般來說若沒有 a, b 互質的假設 a| bc 並不能保證 a| b 或 a| c. 就拿 12| 6×4 來說吧, 很明顯的 12$\nmid$6 (這裡 $\nmid$ 表示不整除的意思) 而且 12$\nmid$4. 同樣的若 a, b 不互質 a| c 且 b| c 也不能保證 ab| c. 例如 4| 12 且 6| 12 但是 4×6$\nmid$12.

接下來我們來看看 a, b 的最小公倍數. 若 l 是 a, b 的最小公倍數, 則由於 gcd (a, b)| l, 我們自然知存在 m, n $\in$ $\mathbb {Z}$ 使得 l = ma + nb. 不過這個表示法對 l 就沒有什麼幫助了. 主要原因是 l 在 {ma + nb | m, n $\in$ $\mathbb {Z}$} 這個集合中不像 gcd(a, b) 有如 Proposition 1.2.4 所述一樣特殊的地位. 不過沒關係, 下一個定理告訴我們一般來說只要了解 a, b 的最大公因數就能掌握 a, b 的最小公倍數.

讓我們先來看看要怎樣知道 l 是 a, b 的最小公倍數. 就如同最大公因數的情形一樣我們要證明兩件事. 首先證明 l 是 a, b 的正的公倍數, 再來就是證明 l 是 a 和 b 的正的公因數中最小的. 如此一來就能擔保 l 是 a, b 的最小公倍數.

Proposition 1.2.8   假設 a, b $\in$ $\mathbb {N}$ 且 gcd(a, b) = d 及 lcm(a, b) = l, 則 l = ab/d. 而且 m $\in$ $\mathbb {Z}$ 是 a, b 的公倍數若且唯若 l| m.

証 明. 由假設 d = gcd(a, b) 知存在 a', b' $\in$ $\mathbb {N}$ 使得 a = a'd, b = b'd 且 gcd(a', b') = 1 (Proposition 1.2.3). 現在我們依上述兩個步驟證明 ab/d = a'b = b'a 是 a, b 的最小公倍數.

首先由 ab/d = b'a 知 a|(ab/d ) 同理知 b|(ab/d ), 也就是說 ab/d 為 a 和 b 的公倍數. 又因為 a, b, d 皆為正數, 所以 ab/d 為 a, b 之正的公倍數.

接著證明若 m 為 a, b 之正的公倍數, 則 (ab/d )$\le$m. 由假設知存在 m', n' $\in$ $\mathbb {N}$ 使得 m = m'a = n'b. 換言之 m = m'a'd = n'b'd, 故消掉 d (因 d$\ne$ 0) 得 m'a' = n'b'. 也就是說 a'| n'b'. 但由於 gcd(a', b') = 1, 故由 Proposition 1.2.7(1) 知 a'| n'. 也就是說存在 h $\in$ $\mathbb {N}$ 使得 n' = a'h. 代回 m = n'b 得 m = ha'b, 故得知 a'b = (ab/d )| m. 由於 ab/d 及 m 皆為正數, 得證 (ab/d )$\le$m. 也就是說 ab/d = lcm(a, b) = l.

既然 ab/d = l 由上面的證明我們知若 m 為 a, b 的公倍數, 則 l = (ab/d )| m. 反之, 若 l| m, 則由 a| l 且 b| l, 得知 a| m 且 b| m, 故 m 為 a, b 之公倍數. $\qedsymbol$

要注意雖然 Proposition 1.2.8 中假設 a, b $\in$ $\mathbb {N}$, 但其目的僅是利用其為正數方便描述最小公倍數. 若 a, b $\in$ $\mathbb {Z}$ 不一定為正時, 我們只要適當的加上負號仍可利用 Proposition 1.2.8 的式子寫下最小公倍數. 另外和 Corollary 1.2.5 中所述公因數為最大公因數之因數相輝映 Proposition 1.2.8 告訴我們公倍數為最小公倍數之倍數.

接下來讓我們來看看有關多個 (多於兩個) 整數的最大公因數性質. 我們試著著推廣前面的方法, 看看前面的結果對多個整數是否適用.

Proposition 1.2.9   假設 a₁,..., a_n $\in$ $\mathbb {N}$, 令 d 為集合 S = {m₁a₁ + ^... + m_na_n | m₁,..., m_n $\in$ $\mathbb {Z}$} 中最小的正整數. 則 gcd(a₁,..., a_n) = d.

証 明. 和前面的情形相同, 利用 well-ordering principle 知 S 中必有最小的正整數. 也就是說敘述中的 d 一定存在. 接著我們要按照前面證明最大公因數的步驟證明 d 為 a₁,..., a_n 的最大公因數.

首先檢查對所有 i $\in$ {1,..., n}, 皆有 d| a_i. 依定義, 存在 m₁,..., m_n $\in$ $\mathbb {Z}$ 使得 d = m₁a₁ + ^... + m_na_n. 利用除法原理我們知對任意 i $\in$ {1,..., n} 皆存在 h_i, r_i $\in$ $\mathbb {Z}$ 使得 a_i = dh_i + r_i, 其中 0$\le$r_i < d. 因此有

r_i = a_i - dh_i = a_i - (m₁a_i + ^... + m_na_n)h_i = - (m₁h_i)a₁ + ^... + (1 - m_ih_i)a_i + ^... - (m_nh_i)a_n.

故得知 r_i $\in$ S. 今若 r_i$\ne$ 0 會導致 r_i 是 S 中小於 d 的一個正整數. 這和當初假設 d 是 S 中最小的正整數相矛盾, 故知 r_i = 0. 也就是說對任意 i = {1,..., n}, 皆有 d| a_i.

接著我們要證明 d 是 a₁,..., a_n 的公因數中最大的數. 也就是要證明若 d' 是 a₁,..., a_n 的公因數, 則 d'$\le$d. 今由於對任意 i $\in$ {1,..., n}, 皆有 d'| a_i 故知 d'| m₁a₁ + ^... + m_na_n. 即 d'| d, 因此由已知 d > 0 當然得 d'$\le$d. $\qedsymbol$

有了 Proposition 1.2.9 我們當然可以和前面的方法一樣得到以下之結果, 證明就不再贅述.

Corollary 1.2.10   假設 a₁,..., a_n $\in$ $\mathbb {N}$ 且 d = gcd(a₁,..., a_n) 則存在 m₁,..., m_n $\in$ $\mathbb {Z}$ 使得 d = m₁a₁ + ^... + m_na_n. 而且對任意 d' $\in$ $\mathbb {Z}$, d' 是 a₁,..., a_n 的公因數若且唯若 d'| d.

要注意並不是所有有關兩個整數的最大公因數的性質都可以推廣到多個整數的情形. 例如 Proposition 1.2.7(2) 告訴我們若 gcd(a, b) = 1 且 a| l 及 b| l, 則 ab| l. 此性質在兩個以上整數的情形就不一定對. 主要原因就是依多個整數互質的定義 a₁, a₂,..., a_n 互質是表示這些數沒有共同的因數但不表示任取其中兩個數都互質. 其實有可能任意 a_i, a_j 都不互質但是 a₁,..., a_n 仍互質. 例如 a₁ = 6, a₂ = 15 以及 a₃ = 10 的情形. 我們有 gcd(a₁, a₂) = 3, gcd(a₂, a₃) = 5 以及 gcd(a₁, a₃) = 2 但是 gcd(a₁, a₂, a₃) = 1. 所以有些情形僅假設 a₁,..., a_n 互質是不夠的, 我們須用到任取兩個都互質 (即對任意 i, j $\in$ {1,..., n} 且 i$\ne$j, 皆有 gcd(a_i, a_j) = 1) 這一個較強的互質性才行. 這種較強的互質性我們稱之為``兩兩互質" (pairwise relatively prime). 當然了若 a₁,..., a_n 兩兩互質, 則 a₁,..., a_n 必互質. 大家一定要清楚這兩種互質性之不同. Proposition 1.2.7(2), 在多個整數的情形之下若改為兩兩互質就會成立. 由於這裡牽涉到任意多個整數, 所以得用到數學歸納法來證明. 數學歸納法的原理我們假設大家在高中時已了解, 此處不再贅述.

Proposition 1.2.11   假設 a₁,..., a_n $\in$ $\mathbb {N}$ 且這些 a_i 兩兩互質. 若令 M = a₁ ^... a_n, 則我們有以下之性質.

1. 對任意 i $\in$ {1,..., n} 皆有 gcd(a_i, M/a_i) = 1.
2. 若對所有 i $\in$ {1,..., n} 皆有 a_i| l, 則 M| l.

証 明. 由於僅在多於一個整數時才談最大公因數, 所以我們數學歸納法從 n = 2 開始.

(1) 此處由於和 a₁,..., a_n 的排序無關, 我們僅處理 i = 1 的情形. 首先看 n = 2 的情形. 此時 M = a₁a₂ 故由假設 gcd(a₁, a₂) = 1 知 gcd(a₁, M/a₁) = 1. 再來由數學歸納法假設 n = k - 1 時成立, 即 gcd(a₁, a₂ ^... a_{k - 1}) = 1, 知存在 m', n' $\in$ $\mathbb {Z}$ 使得

m'a₁ + n'(a₂ ^... a_{k - 1}) = 1. (1.1)

現考慮 n = k 之情形, 此時 M = a₁a₂ ^... a_k. 將式子 (1.1) 兩邊乘以 a_k 得

m'a₁a_k + n'(a₂ ^... a_{k - 1}a_k) = m'a_ka₁ + n'(M/a₁) = a_k. (1.2)

又由兩兩互質的假設知 gcd(a₁, a_k) = 1, 即存在 r, s $\in$ $\mathbb {Z}$ 使得 ra₁ + sa_k = 1. 以式子 (1.2) 之 a_k 代入上式得

1 = ra₁ + s(m'a_ka₁ + n'(M/a₁)) = (r + sm'a_k)a₁ + sn'(M/a₁).

因為 r + sm'a_k $\in$ $\mathbb {Z}$ 且 sn' $\in$ $\mathbb {Z}$ 故由 Corollary 1.2.6 知 gcd(a₁, M/a₁) = 1.

(2) 首先考慮 n = 2 的情形, 此時 M = a₁a₂ 且 gcd(a₁, a₂) = 1 故 Proposition 1.2.7(2) 告訴我們若 a₁| l 且 a₂| l, 則 M| l. 再來由數學歸納法假設 n = k - 1 時成立, 即若令 M' = a₁ ^... a_{k - 1}, 則 M'| l. 現考慮 n = k 之情形, 此時 M = a₁ ^... a_{k - 1}a_k = M'a_k. 由 (1) 知 gcd(a_k, M') = gcd(a_k, M/a_k) = 1, 故由假設 a_k| l 且 M'| l 以及 Proposition 1.2.7(2) 知 M'a_k = M| l. $\qedsymbol$

接下來我們來看, 若我們會求兩個整數的最大公因數 (參見下一節之輾轉相除法) 那麼我們就可以兩個兩個地求得多個整數的最大公因數. 也就是說可以先求 d₁ = gcd(a₁, a₂) 求得 d₂ = gcd(a₁, a₂, a₃) = gcd(d₁, a₃), 這樣一直下去以求得 gcd(a₁, a₂, ^... , a_n). 我們的證明方法還是利用前述證明最大公因數方法進行.

Proposition 1.2.12   若 a₁,..., a_n $\in$ $\mathbb {N}$ (n > 2), 則

gcd(a₁,..., a_{n - 1}, a_n) = gcd(gcd(a₁,..., a_{n - 1}), a_n).

証 明. 令 d = gcd(gcd(a₁,..., a_{n - 1}), a_n) 首先我們要證明 d 是 a₁,..., a_n 的公因數. 由於 d| gcd(a₁,..., a_{n - 1}) 由 Corollary 1.2.10 知 d 是 a₁,..., a_{n - 1} 的公因數. 再加上 d| a_n, 故知 d 是 a₁,..., a_{n - 1}, a_n 的公因數.

現假設 d' 是 a₁,..., a_{n - 1}, a_n 的公因數. 當然 d' 是 a₁,..., a_{n - 1} 的公因數, 故由 Corollary 1.2.10 知 d'| gcd(a₁,..., a_{n - 1}). 再加上 d'| a_n, 故知 d' 是 gcd(a₁,..., a_{n - 1}) 和 a_n 的公因數, 故再由 Corollary 1.2.5 知 d'| gcd(gcd(a₁,..., a_{n - 1}), a_n) = d. 得證 d 是 a₁,..., a_n 的公因數中最大的數, 故為 a₁,..., a_n 的最大公因數. $\qedsymbol$

最後我們看看多個整數的最小公倍數的性質. 首先要注意的是 Proposition 1.2.8 中 lcm(a, b) = ab/gcd(a, b) 這個性質在多個整數時並不一定對. 例如前面所提 a₁ = 6, a₂ = 15 以及 a₃ = 10 的例子, 我們有 a₁a₂a₃ = 900, gcd(a₁, a₂, a₃) = 1 但是 lcm(a₁, a₂, a₃) = 30. 雖然如此, 我們仍有公倍數為最小公倍數之倍數的性質, 而且求多個整數之最小公倍數也可如最大公因數一樣兩個兩個進行. 底下我們將利用數學歸納法同時證明這兩個性質. 這種重要的證明技巧大家或許沒有見過, 不過其原理如同一般的數學歸納法原理, 大家應能理解.

Proposition 1.2.13   若 a₁,..., a_n $\in$ $\mathbb {N}$ (n > 2), 則

lcm(a₁,..., a_{n - 1}, a_n) = lcm(lcm(a₁,..., a_{n - 1}), a_n).

而且 m $\in$ $\mathbb {Z}$ 是 a₁,..., a_n 的公倍數若且唯若 lcm(a₁,..., a_n)| m.

証 明. 應用數學歸納法, 當 n = 3 時令 l = lcm(lcm(a₁, a₂), a₃). 因為 l 為 lcm(a₁, a₂) 和 a₃ 之公倍數, 知 l 為 lcm(a₁, a₂) 之倍數, 故由 Proposition 1.2.8 得知 l 為 a₁, a₂ 的公倍數. 故 l 為 a₁, a₂, a₃ 之公倍數. 現假設 m 為 a₁, a₂, a₃ 之公倍數. 當然 m 是 a₁, a₂ 之公倍數, 故由 Proposition 1.2.8 知 lcm(a₁, a₂)| m. 又因 m 為 a₃ 之倍數, 故知 m 為 lcm(a₁, a₂) 和 a₃ 之公倍數. 因此再由 Proposition 1.2.8 知 l = lcm(lcm(a₁, a₂), a₃)| m. 我們證得了 l 是 a₁, a₂, a₃ 的正公因數中最小的數, 故得 l = lcm(a₁, a₂, a₃). 我們也同時證得 l 整除所有 a₁, a₂, a₃ 的公倍數. 反之, 若 l| m, 則由 a₁| l, a₂| l 以及 a₃| l 知 m 為 a₁, a₂, a₃ 的公倍數. 因此 n = 3 的情形證明完成.

現依數學歸納法假設 n = k - 1 時成立: 即

lcm(a₁,..., a_{k - 1}) = lcm(lcm(a₁,..., a_{k - 2}), a_{k - 1})

且 m $\in$ $\mathbb {Z}$ 是 a₁,..., a_{k - 1} 的公倍數若且唯若 lcm(a₁,..., a_{k - 1})| m. 現考慮 k = n 之情形. 令 l' = lcm(a₁,..., a_{k - 1}) 且 l = lcm(l', a_k) 我們要證明 l 是 a₁,..., a_k 的最小公倍數.

由於 l = lcm(l', a_k) 是 l' = lcm(a₁,..., a_{k - 1}) 的倍數, 故由數學歸納法假設 (n = k - 1 之情況) 知 l 為 a₁,..., a_{k - 1} 的公倍數. 再加上 l 也是 a_k 的倍數, 故得知 l 是 a₁,..., a_k 的公倍數. 另一方面若 m 是 a₁,..., a_{k - 1}, a_k 的公倍數, 當然 m 是 a₁,..., a_{k - 1} 的公倍數. 故由數學歸納法假設知 l' = lcm(a₁,..., a_{k - 1})| m. 再加上 a_k| m, 知 m 為 l' 和 a_k 之公倍數. 故由 Proposition 1.2.8 知 l = lcm(l', a_k)| m. 因而得知 l 確為 a₁,..., a_k 的正公倍數中最小者, 也就是說 l = lcm(a₁,..., a_k). 我們也同時證得若 m 為 a₁,..., a_k 的公倍數, 則 l| m. 反之若 l| m, 則由對所有 i $\in$ {1,..., k} 皆有 a_i| l, 得證 a_i| m. 也就是說 m 為 a₁,..., a_k 的公倍數. $\qedsymbol$