Chapter 1 整數的基本性質 雖然有些同學已對整數的性質相當了解, 我們想利用這個大家較熟悉的東西來介紹一下如何用比較 數學 的方法來處理問題. 有些簡單的問題我們可能會故意繞遠路來處理, 主要原因是希望大家能熟悉表達數學的方法和形式以及邏輯推演的過程. 所以這一章會顯得較為冗長. 若大家對這

Transcription

1 基礎數論 李華介國立台灣師範大學數學系

2 Chapter 1 整數的基本性質 雖然有些同學已對整數的性質相當了解, 我們想利用這個大家較熟悉的東西來介紹一下如何用比較 數學 的方法來處理問題. 有些簡單的問題我們可能會故意繞遠路來處理, 主要原因是希望大家能熟悉表達數學的方法和形式以及邏輯推演的過程. 所以這一章會顯得較為冗長. 若大家對這些性質已很熟悉且認為表達數學的能力已很成熟, 可以略過此章, 直接進入下一章 因數與倍數 首先我們介紹幾個符號順便複習一下集合的概念. 要知道符號是數學上幫助我們能簡明表達事情的必要工具, 大家應該要學習如何適切的使用符號. 在本講義中我們用 Z 來表示所有整數所成的集合. 所以 0 在 Z 中, 2 也在 Z 中, 2007 和 365 也在 Z 中. 這樣一來當我們要說一個數 a 是整數時, 我們只要說 a 在 Z 中就好了. 在數學上我們要說一個東西在一個集合中就用 這個符號, 也就是 屬於 的意思. 所以以後我們要表達 a 是一個整數就直接說 a Z 即可. 我們也常只考慮正整數, 在本講義中我們用 N 表示所有正整數所成的集合. 所以我們用 a N 來表示 a 是一個正整數. 對於整數一開始是由自然數出發, 利用數數的方法我們定義了加法, 接著有了負的概念整個整數加法的體系就建立起來了 給定 a Z, 我們用 2a 表示. a + a 一般來說若 n N 我們將 n 個 a 相加的結果表為 na. 我們也將 ( n)a 看成 n 個 a 相加所得之值. 若我們再將 0a 定為 0, 如此一來對任意的 m Z, ma 都有了定義. 如此定義出來的乘法和加法之間所滿足的運算規則如交換率, 結合率和分配率等此處就不再贅述. 我們將可以寫成 ma 其中 m Z 的數稱為 a 的倍數 (multiple). 另一方面若 b 是 a 的倍數, 我們也稱 a 是 b 的因數 (divisor). 符號記為 a b. 我們將 a 的倍數所成的集合用 az 來表示. 也就是說 az 中的元素都是 ma 這樣的形式其中 m Z. 這樣的集合可用 az = {ma m Z} 來表示. 因此我們可以說 b az 和 b 是 a 的倍數 ( 或 a 是 b 的因數 ) 是一樣的意思. 1

3 2 1. 整數的基本性質 接下來我們想用集合的角度處理因數倍數的一些性質. 要注意這些性質大家高中時都已證過, 我們用集合的角度處理並沒有比較方便, 介紹這樣的處理方法僅是利用它讓大家熟悉一下集合的語言. 首先注意若 a Z, az 這一個集合並不單單是一個集合. 由於整數在加法和乘法之下有所謂的封閉性, az 也有以下兩個重要的封閉性. Proposition 假設 a Z 且 b, c az. 則我們有以下之性質. (1) b + c az. (2) 對任意 m Z 皆有 mb az. Proof. 因為 b, c az 依定義知存在 n, n Z 使得 b = na 且 c = n a. (1) 由分配率知 b + c = na + n a = (n + n )a. 又由於 n, n Z 我們知 n + n Z, 故得 b + c az. (2) 由結合率知 mb = m(na) = (mn)a. 又由於 m, n Z 我們知 mn Z, 故得 mb az. 結合 Proposition 的結果我們有以下之性質. Corollary 假設 a Z 且 b, c az. 若 m, n Z 則 mb + nc az. 換言之, 若 a b 且 a c, 則對任意 m, n Z 皆有 a mb + nc. Proof. 因為 b, c az 以及 m, n Z, 由 Proposition 1.1.1(2) 知 mb, nc az. 再利用 Proposition 1.1.1(1) 知 mb + nc az. 也就是說 a mb + nc. 大部分一個重要的性質我們都會用 Proposition 來稱呼再冠上編號以便以後引用. 而直接套用 Proposition 所得的性質我們都用 Corollary 來稱呼. 接著我們來看集合單純的性質. 若 A, B 是集合且 A 中的元素都在 B 中, 則我們就用 A B 來表示 ( 稱 A 包含於 B). 很容易有以下之性質 : (1) 若 A B 且 B A 則 A = B. (2) 若 A B 且 B C 則 A C. 結合這集合的性質以及前面提的封閉性我們有以下之結果. Proposition 假設 a, b, c Z. 我們有以下之結果. (1) bz az 若且唯若 a b. (2) 若 a b 且 b a 則 a = ±b. (3) 若 a b 且 b c 則 a c. Proof. (1) 若 bz az, 由於 b bz, 我們得 b az. 故知 a b. 反之, 若 a b, 我們要證明 bz az. 一般來說要證明一個集合 B 包含於另一個集合 A, 我們要證明的是 B 中任取一個元素都會在 A 中. 因此此處我們要證的是任取 bz 中的一個元素 mb, 其中 m Z 都可以

4 1.1. 因數與倍數 3 得到 mb az. 然而由 a b 的假設我們知 b az. 接著我們就可利用 Proposition 1.1.1(2) 知對任意 m Z 皆有 mb az. 也就是說 bz 的元素都在 az 中. 故得證 bz az. (2) 若 a b 且 b a, 由 (1) 知 bz az 且 az bz. 因此由集合性質知 az = bz. 也就是說 az 和 bz 是相同的集合. 由此, 很容易看出當 a = 0 時 b = 0. 反之亦然. 因此我們只剩考慮 a 0 且 b 0 的情況. 此時 az 中最小的正數 a ( 當 a > 0) 或 a ( 當 a < 0) 會等於 bz 中最小的正數 b 或 b. 故得證 a = ±b. (3) 若 a b 且 b c, 則由 (1) 知 bz az 且 cz bz. 因此由集合性質知 cz az. 故再由 (1) 的等價關係知 a c. Remark 對於整數有一個很重要的性質 well-ordering principle. 這一個 principle 就是說給定一個非空的整數的子集合 S, 如果 S 有下界 ( 若有一數小於 S 中所有的數, 則稱 S 有下界 ), 則 S 中必含有一個最小的整數 ( 通常用 min S 來表示 ). 同理若整數的非空子集合 S 有上界 ( 若有一數大於 S 中所有的數, 則稱 S 有上界 ), 則此集合中必含有一個最大的整數 ( 通常用 max S 來表示 ). 例如剛才 Proposition 1.1.3(2) 的證明中我們考慮 az 中最小的正整數, 當 a > 0 時 a 就是 az 中最小的正整數. 這裡因為我們確實知道 az 這個集合長什麼樣, 所以並不需這個性質直接可知 a 就是最小的. 以後我們常會碰到一些抽象的正整數子集合, 那時就得經常用到整數的這個性質來確知此集合存在一個最小的正數. 另外要注意此性質在其他的情況如有理數就不對了. 事實上正有理數是有下界的 (0 小於所有的正有理數 ), 但並沒有所謂最小的正有理數. 再次強調一下前面我們用集合較抽象的方法證明整除的性質主要是要大家習慣集合的語言以及學習一些抽象的論證方法. 它並不是什麼特別的好方法. 比方說大家熟知的 a b 則 ma mb 就很難用類似上面集合的方法來處理. 總之, 要處裡一個問題並沒有說一定要用什麼方法. 你只要使用一個你認為可行且正確的方法處理. 所以學習數學絕不要僅是背誦定理的證明. 如何將繁瑣的證明整理成你自己習慣且能理解的語言才是重點. 接下來我們就回歸定義來證明前述之性質. Lemma 假設 a, b Z 且 a b, 我們有以下之性質. (1) 若 m Z, 則 ma mb. (2) 若 d a 且 d b, 則 (a/d) (b/d). Proof. 由假設 a b 知存在 n Z 使得 b = na. (1) 將等式兩邊同乘以 m 可得 mb = mna = n(ma) 故知 ma mb. (2) d a 且 d b 即表示存在 a, b Z 使得 a = a d 且 b = b d. 故由 b = na 得 b d = na d. 0, 兩邊同除以 d 可得 b = na, 即 a b. 因為 a/d = a 且 b/d = b 故得證 因為 d = (a/d) (b/d). Lemma 是一個簡單的性質. 它本身並不算什麼重大的性質, 但是以後討論許多性質時都要用到它, 我們便用 Lemma 稱呼之以方便引用.

5 4 1. 整數的基本性質 在 Lemma 1.1.5(2) 中 d a 且 d b 的假設就是說 d 同時是 a 和 b 的因數, 我們簡稱之為 a, b 的公因數. 討論一些整數之間的關係時公因數和最大公因數以及公倍數和最小公倍數是很重要的工具. 接下來我們是給它們下一個定義. Definition 令 a 1, a 2,..., a n Z. (1) 若 c Z, 且 c a 1, c a 2,..., c a n, 則稱 c 為 a 1, a 2,..., a n 的公因數 (common divisor). (2) 若 d N 是 a 1, a 2,..., a n 的公因數中最大的, 則稱 d 為 a 1, a 2,..., a n 的最大公因數 greatest common divisor, 通常我們會用 gcd(a 1, a 2,..., a n ) 來表示之. (3) 若 m Z, 且 a 1 m, a 2 m,..., a n m, 則稱 m 為 a 1, a 2,..., a n 的公倍數 (common multiple). (4) 若 l N 是 a 1, a 2,..., a n 的正的公倍數中最小的, 則稱 l 為 a 1, a 2,..., a n 的最小公倍數 least common divisor, 通常我們會用 lcm(a 1, a 2,..., a n ) 來表示之. 通常當有一個符號或名詞需要介紹時, 為了方便找到我們會特別用 Definition 來標示之. 當要下一個定義時要注意是否合理. 不要給的定義的東西根本不存在或沒有用. Definition 中就要注意最大公因數及最小公倍數是否存在 : 因為 1 整除所有的整數, 所以若 a 1, a 2,..., a n Z 則其公因數必存在. 又因為 a 1, a 2,..., a n 有有限多個公因數, 所以我們知 a 1, a 2,..., a n 的最大公因數必存在. 不過 a 1, a 2,..., a n 的最大公因數有可能是 1. 若如此 ( 即 gcd(a 1, a 2,..., a n ) = 1), 則稱 a 1, a 2,..., a n 互質 (relatively prime). 另一方面因為 a 1 a 2 a n 是 a 1, a 2,..., a n 的公倍數, 所以適當的乘上正負號可知 a 1, a 2,..., a n 正的公倍數必存在, 因此由 well-ordering principle 知 a 1, a 2,..., a n 的最小公倍數必存在. 下一節我們將會談論最大公因數及最小公倍數的一些基本性質 除法原理 整數中最基本的定理應該就是整數的除法原理 Division Algorithm, 幾乎所有整數的基本性質都是由它推導出來. Theorem (Division Algorithm). 給定一正整數 n, 對任意的 m Z, 皆存在 h, r Z, 其中 0 r < n, 滿足 m = h n + r. 這是一個很重要的性質, 重要到我們以 Theorem 來稱呼它. 這個定理我們習慣稱為除法原理, 如此稱它當然就包含 除 這個概念. 不過因為我們現在僅談加 ( 減 ) 法和乘法的性質, 我們避免用除的概念. Proof. 給定 n N 且 m Z. 首先考慮 W = {m t n t Z} 這一個集合. 也就是收集 m, m n, m 2n,... 以及 m + n, m + 2n,... 等元素所得集合. 因為 t 可取任何整數, 很容易就看出 W 一定包含一些非負的整數. 換言之, 若考慮 W 為 W 中非負的元素所成的集合, 則 W 是一個非空的整數的子集合. 故由整數的 well-ordering principle 知 W 中存

6 1.2. 除法原理 5 在最小的整數 r. 即 r 是 W 中最小的非負的整數. 因為 r W, 由定義知存在 h Z 滿足 r = m h n. 我們最主要的目的就是要證明 0 r < n. 假設 r 不合我們的條件, 也就是說 r n ( 別忘了 r 是非負整數的假設 ). 若如此, 我們可將 r 寫成 r = n + r, 其中 r 0. 因此利用 m = h n + r = h n + (n + r ) = (h + 1) n + r, 我們得到 r = m (h + 1) n W. 但 0 r < r, 這和 r 是 W 中最小的非負整數相矛盾. 故得證本定理. 要注意 Theorem 的證明我們用到整數上可以排序的 well-ordering principle, 因此雖然證明很簡單, 但並不能直接套用到其他的數系. 接下來我們就要利用除法原理來探討公因數及最大公因數的基本性質. 由於 a 和 a 的因數是一樣的, 所以不失一般性, 在討論因數時我們僅討論正整數的情形. 我們就從兩個正整數的情形開始討論. Proposition 假設 a, b N 且 d 是 a 和 b 的公因數. 若 d 是 a/d 和 b/d 的公因數, 則 dd 是 a 和 b 的公因數. Proof. 首先注意, 由於 d 是 a, b 的公因數, 故存在 m, n Z 使得 a = dm 且 b = dn. 也就是說 a/d = m 和 b/d = n 皆為整數. 又 d 是 m, n 的公因數故存在 m, n Z 使得 m = d m 且 n = d n. 整理得 a = dd m 且 b = dd n 故知 dd 是 a 和 b 的公因數. 若 Proposition 中我們取 d = gcd(a, b), 則利用最大公因數的定義我們可得以下之性質. Corollary 假設 a, b N 且 d = gcd(a, b). 則 a/d 和 b/d 互質. Proof. 要證明 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 知 dd 是 a, b 的公因數. 然而已知 d 是 a, b 公因數中最大的, 故知 d dd. 也就是說 d 1. 因此結合當初假設 d 是 a, b 的一個正的公因數 ( 即 d 1) 得證 d = 1. 一般要證明 d = gcd(a, b) 我們要證明兩件事. 首先要證明 d 是 a, b 的公因數, 再來就是證明 d 是 a 和 b 的公因數中最大的. 前面 Corollary 中我們要證明 gcd(a/d, b/d) = 1. 由於 1 必為 a/d, b/d 的公因數, 所以只要證明任意 a/d 和 b/d 的公因數皆小於等於 1 就可. 接著我們來看另一個最大公因數的性質順便在證明中學習證明最大公因數的方法. Proposition 假設 a, b N, 令 d 為集合 S = {ma + nb m, n Z} 中最小的正整數. 則 gcd(a, b) = d. Proof. 首先注意由於這裡 m, n 是任意的整數, 所以我們知道集合 S = {ma+nb m, n Z} 中必存在正整數. 所以 S 中的正整數必形成一個非空的子集合, 因此我們套用 well-ordering

7 6 1. 整數的基本性質 principle 知 S 中必有最小的正整數. 也就是說敘述中的 d 一定存在. 接著我們要按照前面提的兩個步驟證明 d 為 a, b 的最大公因數. 首先檢查 d a 且 d b. 依定義存在 m, n Z 使得 d = ma + nb. 要檢查是否 d a 直覺的方法就是將 a 除以 d 看看是否餘數為 0. 利用除法原理我們知存在 h, r Z 使得 a = dh + r, 其中 0 r < d. 因此有 r = a dh = a (ma + nb)h = (1 mh)a (nh)b. 由於 1 mh 和 nh 皆為整數依定義知 r S. 今若 r = 0 會導致 r 是 S 中小於 d 的一個正整數. 這和當初假設 d 是 S 中最小的正整數相矛盾, 故知 r = 0. 也就是說 d a. 同理可證 d b. 接著我們要證明 d 是 a, b 的公因數中最大的數. 也就是要證明若 d 是 a, b 的公因數, 則 d d. 今由於 d a 且 d b 由 Corollary 知 d ma + nb. 即 d d, 也就是說存在 l Z 使得 d = d l. 因此由已知 d > 0 當然得 d d. 在上面證明 d 除以 a 的餘數為 0 的過程中. 我們無法直接證明餘數為 0, 不過發現若餘數不為 0 的話會導致矛盾的結果, 因而確知其餘數非為 0 不可. 這樣證明的方法就是所謂的 反證法. 這樣的證明方法我們以後還會經常看到. 或許大家會奇怪, 一般來說找 a, b 的最大公因數只要在 a, b 有限多個公因數中找最大的就好了為什麼要自討苦吃在 {ma + nb m, n Z} 這個有無窮多個元素的集合中找? 沒有錯如果 a, b 很具體的知道是什麼當然直接找, 然而當我們要討論一般的情形 a, b 是任何可能的整數不能用幾個具體例子代一代就了事. 所以雖然 Proposition 在實際操作時並不實用但要用到理論的推演時他卻是很好用來表達最大公因數的工具. 直接利用 Proposition 我們馬上有以下之性質. Corollary 假設 a, b N 且 d = gcd(a, b) 則存在 m, n Z 使得 d = ma + nb. 而且對任意 d Z, d 是 a, b 的公因數若且唯若 d d. Proof. 由 Proposition 我們知 d 在集合 S = {ma + nb m, n Z} 中, 故依定義存在 m, n Z 使得 d = ma + nb. 注意這裡 若且唯若 的意思就是說如果 d 是 a, b 的公因數那麼 d 必整除 a, b 的最大公因數 d, 反之若 d 整除 a, b 的最大公因數, 那麼 d 一定是 a, b 的公因數. 由 Proposition 的證明我們知若 d 是 a, b 的公因數則 d d. 反之若 d d, 則由於 d a 且 d b, 利用 Proposition 1.1.3(3) 知 d a 且 d b. 即 d 為 a, b 的公因數. 一般來說有的性質可以從甲可推得乙, 但這並不表示從乙可推得甲. 如果兩個性質可以互推, 我們就用 若且唯若 表示之. 特別要注意 Corollary 並不是說若有一個正整數 d 可找到 m, n Z 使得 d = ma + nb, 則 d 就是 a, b 的公因數. 這是一開始大家在學習邏輯推論時常犯的錯誤. 其實 d 可以寫成 ma + nb 僅表示 d 會在集合 S = {ma + nb m, n Z} 中, 並不表示 d 會是 S 中最小的正整數. 所以當然 d 就未必是 a, b 的最大公因數. 因此當你要證明 d 是 a, b 的最大公因數時, 還是得按部就班如前面所提的兩步驟進行, 千萬不要

8 1.2. 除法原理 7 找到兩個整數 m, n 使得 d = ma + nb 就說 d 就是 a, b 的最大公因數. 當然了如果你要證明 a, b 互質 ( 即 gcd(a, b) = 1) 時可以利用找到 m, n 使得 ma + nb = 1 來處理. 這是因為此時 1 在 S 中, 故當然是 S 中最小的正整數了. 因此我們將此特殊情況列出. Corollary 假設 a, b N. 則 gcd(a, b) = 1 若且唯若存在 m, n Z 使得 ma+nb = 1. Proof. 再強調一次, 要證明若且唯若必需兩個方向都證明. 若 gcd(a, b) = 1, 由 Corollary 知存在 m, n Z 使得 1 = ma + nb. 反之, 若存在 m, n Z 使得 ma + nb = 1, 則 1 必為集合 {ma + nb m, n Z} 中最小的正整數, 故由 Proposition 知 gcd(a, b) = 1. 以上的性質並沒有告訴我們怎麼找到 m, n 使得 ma + nb = gcd(a, b), 我們將會在下節介紹完輾轉相除法後給一個方法來求 m, n. 雖然目前我們不知如何求得 m, n, 不過從下一個探討 a, b 互質時的重要的性質我們可以看到僅僅知道它們的存在性在理論的推演就很管用了. Proposition 假設 a, b N 且 gcd(a, b) = 1. 我們有以下的性質 : (1) 若 k Z 且 a bk, 則 a k. (2) 若 l Z 且 a l 及 b l, 則 ab l. Proof. 因為 gcd(a, b) = 1, 由 Corollary 我們知存在 m, n Z 使得 ma + nb = 1. (1) 將 ma + nb = 1 等式兩邊乘上 k 可得 mak + nbk = k. 然而假設 a bk 故利用 a ak 以及 Corollary 知 a k. (2) 由 a l 以及 b l 知存在 r, s Z 使得 l = ar = bs. 因為 a ar 故得 a bs. 再由 gcd(a, b) = 1 的假設利用 (1) 可得 a s. 換言之存在 t Z 使得 s = at. 將之帶回 l = bs 得 l = bat, 得證 ab l. 要注意 Proposition 的條件. 一般來說若沒有 a, b 互質的假設 a bc 並不能保證 a b 或 a c. 就拿 來說吧, 很明顯的 12 6 ( 這裡 表示不整除的意思 ) 而且 同樣的若 a, b 不互質 a c 且 b c 也不能保證 ab c. 例如 4 12 且 6 12 但是 接下來我們來看看 a, b 的最小公倍數. 若 l 是 a, b 的最小公倍數, 則由於 gcd(a, b) l, 我們自然知存在 m, n Z 使得 l = ma + nb. 不過這個表示法對 l 就沒有什麼幫助了. 主要原因是 l 在 {ma + nb m, n Z} 這個集合中不像 gcd(a, b) 有如 Proposition 所述一樣特殊的地位. 不過沒關係, 下一個定理告訴我們一般來說只要了解 a, b 的最大公因數就能掌握 a, b 的最小公倍數. 讓我們先來看看要怎樣知道 l 是 a, b 的最小公倍數. 就如同最大公因數的情形一樣我們要證明兩件事. 首先證明 l 是 a, b 的正的公倍數, 再來就是證明 l 是 a 和 b 的正的公因數中最小的. 如此一來就能擔保 l 是 a, b 的最小公倍數. Proposition 假設 a, b N 且 gcd(a, b) = d 及 lcm(a, b) = l, 則 l = ab/d. 而且 m Z 是 a, b 的公倍數若且唯若 l m.

9 8 1. 整數的基本性質 Proof. 由假設 d = gcd(a, b) 知存在 a, b 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) m. 由假設知存在 m, n N 使得 m = m a = n b. 換言之 m = m a d = n b d, 故消掉 d ( 因 d = 0) 得 m a = n b. 也就是說 a n b. 但由於 gcd(a, b ) = 1, 故由 Proposition 1.2.7(1) 知 a n. 也就是說存在 h N 使得 n = a h. 代回 m = n b 得 m = ha b, 故得知 a b = (ab/d) m. 由於 ab/d 及 m 皆為正數, 得證 (ab/d) 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 之公倍數. 要注意雖然 Proposition 中假設 a, b N, 但其目的僅是利用其為正數方便描述最小公倍數. 若 a, b Z 不一定為正時, 我們只要適當的加上負號仍可利用 Proposition 的式子寫下最小公倍數. 另外和 Corollary 中所述公因數為最大公因數之因數相輝映 Proposition 告訴我們公倍數為最小公倍數之倍數. 接下來讓我們來看看有關多個 ( 多於兩個 ) 整數的最大公因數性質. 我們試著著推廣前面的方法, 看看前面的結果對多個整數是否適用. Proposition 假設 a 1,..., a n N, 令 d 為集合 S = {m 1 a m n a n m 1,..., m n Z} 中最小的正整數. 則 gcd(a 1,..., a n ) = d. Proof. 和前面的情形相同, 利用 well-ordering principle 知 S 中必有最小的正整數. 也就是說敘述中的 d 一定存在. 接著我們要按照前面證明最大公因數的步驟證明 d 為 a 1,..., a n 的最大公因數. 首先檢查對所有 i {1,..., n}, 皆有 d a i. 依定義, 存在 m 1,..., m n Z 使得 d = m 1 a m n a n. 利用除法原理我們知對任意 i {1,..., n} 皆存在 h i, r i Z 使得 a i = dh i + r i, 其中 0 r i < d. 因此有 r i = a i dh i = a i (m 1 a i + +m n a n )h i = (m 1 h i )a 1 + +(1 m i h i )a i + (m n h i )a n. 故得知 r i S. 今若 r i = 0 會導致 r i 是 S 中小於 d 的一個正整數. 這和當初假設 d 是 S 中最小的正整數相矛盾, 故知 r i = 0. 也就是說對任意 i = {1,..., n}, 皆有 d a i. 接著我們要證明 d 是 a 1,..., a n 的公因數中最大的數. 也就是要證明若 d 是 a 1,..., a n 的公因數, 則 d d. 今由於對任意 i {1,..., n}, 皆有 d a i 故知 d m 1 a m n a n. 即 d d, 因此由已知 d > 0 當然得 d d. 有了 Proposition 我們當然可以和前面的方法一樣得到以下之結果, 證明就不再贅述.

10 1.2. 除法原理 9 Corollary 假設 a 1,..., a n N 且 d = gcd(a 1,..., a n ) 則存在 m 1,..., m n Z 使得 d = m 1 a m n a n. 而且對任意 d Z, d 是 a 1,..., a n 的公因數若且唯若 d d. 要注意並不是所有有關兩個整數的最大公因數的性質都可以推廣到多個整數的情形. 例如 Proposition 1.2.7(2) 告訴我們若 gcd(a, b) = 1 且 a l 及 b l, 則 ab l. 此性質在兩個以上整數的情形就不一定對. 主要原因就是依多個整數互質的定義 a 1, a 2,..., a n 互質是表示這些數沒有共同的因數但不表示任取其中兩個數都互質. 其實有可能任意 a i, a j 都不互質但是 a 1,..., a n 仍互質. 例如 a 1 = 6, a 2 = 15 以及 a 3 = 10 的情形. 我們有 gcd(a 1, a 2 ) = 3, gcd(a 2, a 3 ) = 5 以及 gcd(a 1, a 3 ) = 2 但是 gcd(a 1, a 2, a 3 ) = 1. 所以有些情形僅假設 a 1,..., a n 互質是不夠的, 我們須用到任取兩個都互質 ( 即對任意 i, j {1,..., n} 且 i = j, 皆有 gcd(a i, a j ) = 1) 這一個較強的互質性才行. 這種較強的互質性我們稱之為 兩兩互質 (pairwise relatively prime). 當然了若 a 1,..., a n 兩兩互質, 則 a 1,..., a n 必互質. 大家一定要清楚這兩種互質性之不同. Proposition 1.2.7(2), 在多個整數的情形之下若改為兩兩互質就會成立. 由於這裡牽涉到任意多個整數, 所以得用到數學歸納法來證明. 數學歸納法的原理我們假設大家在高中時已了解, 此處不再贅述. Proposition 假設 a 1,..., a n N 且這些 a i 兩兩互質. 若令 M = a 1 a n, 則我們有以下之性質. (1) 對任意 i {1,..., n} 皆有 gcd(a i, M/a i ) = 1. (2) 若對所有 i {1,..., n} 皆有 a i l, 則 M l. Proof. 由於僅在多於一個整數時才談最大公因數, 所以我們數學歸納法從 n = 2 開始. (1) 此處由於和 a 1,..., a n 的排序無關, 我們僅處理 i = 1 的情形. 首先看 n = 2 的情形. 此時 M = a 1 a 2 故由假設 gcd(a 1, a 2 ) = 1 知 gcd(a 1, M/a 1 ) = 1. 再來由數學歸納法假設 n = k 1 時成立, 即 gcd(a 1, a 2 a k 1 ) = 1, 知存在 m, n Z 使得 m a 1 + n (a 2 a k 1 ) = 1. (1.1) 現考慮 n = k 之情形, 此時 M = a 1 a 2 a k. 將式子 (1.1) 兩邊乘以 a k 得 m a 1 a k + n (a 2 a k 1 a k ) = m a k a 1 + n (M/a 1 ) = a k. (1.2) 又由兩兩互質的假設知 gcd(a 1, a k ) = 1, 即存在 r, s Z 使得 ra 1 + sa k = 1. 以式子 (1.2) 之 a k 代入上式得 1 = ra 1 + s(m a k a 1 + n (M/a 1 )) = (r + sm a k )a 1 + sn (M/a 1 ). 因為 r + sm a k Z 且 sn Z 故由 Corollary 知 gcd(a 1, M/a 1 ) = 1. (2) 首先考慮 n = 2 的情形, 此時 M = a 1 a 2 且 gcd(a 1, a 2 ) = 1 故 Proposition 1.2.7(2) 告訴我們若 a 1 l 且 a 2 l, 則 M l. 再來由數學歸納法假設 n = k 1 時成立, 即若令 M = a 1 a k 1, 則 M l. 現考慮 n = k 之情形, 此時 M = a 1 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.

11 10 1. 整數的基本性質 接下來我們來看, 若我們會求兩個整數的最大公因數 ( 參見下一節之輾轉相除法 ) 那麼我們就可以兩個兩個地求得多個整數的最大公因數. 也就是說可以先求 d 1 = gcd(a 1, a 2 ) 求得 d 2 = gcd(a 1, a 2, a 3 ) = gcd(d 1, a 3 ), 這樣一直下去以求得 gcd(a 1, a 2,, a n ). 我們的證明方法還是利用前述證明最大公因數方法進行. Proposition 若 a 1,..., a n N (n > 2), 則 gcd(a 1,..., a n 1, a n ) = gcd(gcd(a 1,..., a n 1 ), a n ). Proof. 令 d = gcd(gcd(a 1,..., a n 1 ), a n ) 首先我們要證明 d 是 a 1,..., a n 的公因數. 由於 d gcd(a 1,..., a n 1 ) 由 Corollary 知 d 是 a 1,..., a n 1 的公因數. 再加上 d a n, 故知 d 是 a 1,..., a n 1, a n 的公因數. 現假設 d 是 a 1,..., a n 1, a n 的公因數. 當然 d 是 a 1,..., a n 1 的公因數, 故由 Corollary 知 d gcd(a 1,..., a n 1 ). 再加上 d a n, 故知 d 是 gcd(a 1,..., a n 1 ) 和 a n 的公因數, 故再由 Corollary 知 d gcd(gcd(a 1,..., a n 1 ), a n ) = d. 得證 d 是 a 1,..., a n 的公因數中最大的數, 故為 a 1,..., a n 的最大公因數. 最後我們看看多個整數的最小公倍數的性質. 首先要注意的是 Proposition 中 lcm(a, b) = ab/ gcd(a, b) 這個性質在多個整數時並不一定對. 例如前面所提 a 1 = 6, a 2 = 15 以及 a 3 = 10 的例子, 我們有 a 1 a 2 a 3 = 900, gcd(a 1, a 2, a 3 ) = 1 但是 lcm(a 1, a 2, a 3 ) = 30. 雖然如此, 我們仍有公倍數為最小公倍數之倍數的性質, 而且求多個整數之最小公倍數也可如最大公因數一樣兩個兩個進行. 底下我們將利用數學歸納法同時證明這兩個性質. 這種重要的證明技巧大家或許沒有見過, 不過其原理如同一般的數學歸納法原理, 大家應能理解. Proposition 若 a 1,..., a n N (n > 2), 則 lcm(a 1,..., a n 1, a n ) = lcm(lcm(a 1,..., a n 1 ), a n ). 而且 m Z 是 a 1,..., a n 的公倍數若且唯若 lcm(a 1,..., a n ) m. Proof. 應用數學歸納法, 當 n = 3 時令 l = lcm(lcm(a 1, a 2 ), a 3 ). 因為 l 為 lcm(a 1, a 2 ) 和 a 3 之公倍數, 知 l 為 lcm(a 1, a 2 ) 之倍數, 故由 Proposition 得知 l 為 a 1, a 2 的公倍數. 故 l 為 a 1, a 2, a 3 之公倍數. 現假設 m 為 a 1, a 2, a 3 之公倍數. 當然 m 是 a 1, a 2 之公倍數, 故由 Proposition 知 lcm(a 1, a 2 ) m. 又因 m 為 a 3 之倍數, 故知 m 為 lcm(a 1, a 2 ) 和 a 3 之公倍數. 因此再由 Proposition 知 l = lcm(lcm(a 1, a 2 ), a 3 ) m. 我們證得了 l 是 a 1, a 2, a 3 的正公因數中最小的數, 故得 l = lcm(a 1, a 2, a 3 ). 我們也同時證得 l 整除所有 a 1, a 2, a 3 的公倍數. 反之, 若 l m, 則由 a 1 l, a 2 l 以及 a 3 l 知 m 為 a 1, a 2, a 3 的公倍數. 因此 n = 3 的情形證明完成. 現依數學歸納法假設 n = k 1 時成立 : 即 lcm(a 1,..., a k 1 ) = lcm(lcm(a 1,..., a k 2 ), a k 1 ) 且 m Z 是 a 1,..., a k 1 的公倍數若且唯若 lcm(a 1,..., a k 1 ) m. 現考慮 k = n 之情形. 令 l = lcm(a 1,..., a k 1 ) 且 l = lcm(l, a k ) 我們要證明 l 是 a 1,..., a k 的最小公倍數.

12 1.3. 輾轉相除法 11 由於 l = lcm(l, a k ) 是 l = lcm(a 1,..., a k 1 ) 的倍數, 故由數學歸納法假設 (n = k 1 之情況 ) 知 l 為 a 1,..., a k 1 的公倍數. 再加上 l 也是 a k 的倍數, 故得知 l 是 a 1,..., a k 的公倍數. 另一方面若 m 是 a 1,..., a k 1, a k 的公倍數, 當然 m 是 a 1,..., a k 1 的公倍數. 故由數學歸納法假設知 l = lcm(a 1,..., a k 1 ) m. 再加上 a k m, 知 m 為 l 和 a k 之公倍數. 故由 Proposition 知 l = lcm(l, a k ) m. 因而得知 l 確為 a 1,..., a k 的正公倍數中最小者, 也就是說 l = lcm(a 1,..., a k ). 我們也同時證得若 m 為 a 1,..., a k 的公倍數, 則 l m. 反之若 l m, 則由對所有 i {1,..., k} 皆有 a i l, 得證 a i m. 也就是說 m 為 a 1,..., a k 的公倍數 輾轉相除法 輾轉相除法是求最大公因數很有效率的方法. 首先我們介紹輾轉相除法的原理. Lemma 若 a, b N 且 a = bh + r, 其中 h, r Z, 則 gcd(a, b) = gcd(b, r). Proof. 假設 d 1 = gcd(a, b) 且 d 2 = gcd(b, r). 我們證明 d 1 d 2 且 d 2 d 1, 因而可利用 Proposition 1.1.3(2) 以及 d 1, d 2 皆為正數得證 d 1 = d 2. 因 d 1 a 且 d 1 b 利用 Corollary 我們知 d 1 a bh = r. 因為 d 1 b, d 1 r 且 d 2 = gcd(b, r) 故由 Proposition 知 d 1 d 2. 另一方面, 因為 d 2 b 且 d 2 r 故 d 2 bh + r = a. 因此可得 d 2 d 1. Lemma 告訴我們當 a > b > 0 時, 要求 a, b 的最大公因數我們可以先將 a 除以 b 所得餘數若為 r, 則 a, b 的最大公因數等於 b 和 r 的最大公因數. 因為 0 r < b < a, 所以當然把計算簡化了. 接著我們就來看看輾轉相除法. 由於 gcd(a, b) = gcd( a, b) 所以我們只要考慮 a, b 都是正整數的情況. Theorem (The Euclidean Algorithm). 假設 a, b N 且 a > b. 由除法原理我們知存在 h 0, r 0 Z 使得 a = bh 0 + r 0, 其中 0 r 0 < b. 若 r 0 > 0, 則存在 h 1, r 1 Z 使得 b = r 0 h 1 + r 1, 其中 0 r 1 < r 0. 若 r 1 > 0, 則存在 h 2, r 2 Z 使得 r 0 = r 1 h 2 + r 2, 其中 0 r 2 < r 1. 如此繼續下去直到 r n = 0 為止. 若 n = 0 ( 即 r 0 = 0), 則 gcd(a, b) = b. 若 n 1, 則 gcd(a, b) = r n 1. Proof. 首先注意若 r 0 = 0, 由於 r 0 > r 1 > r 2 >... 是嚴格遞減的, 因為 r 0 和 0 之間最多僅能插入 r 0 1 個正整數, 所以我們知道一定會有 n r 0 使得 r n = 0.

13 12 1. 整數的基本性質 若 r 0 = 0, 即 a = bh 0, 故知 b 為 a 之因數, 得證 b 為 a, b 的最大公因數. 若 r 0 > 0, 則由 Lemma 知 gcd(a, b) = gcd(b, r 0 ) = gcd(r 0, r 1 ) = = gcd(r n 1, r n ) = gcd(r n 1, 0) = r n 1. 現在我們來看用輾轉相除法求最大公因數的例子. Example 我們求 a = 481 和 b = 221 的最大公因數. 首先由除法原理得 481 = , 知 r 0 = 39. 因此再考慮 b = 221 除以 r 0 = 39 得 221 = , 知 r 1 = 26. 再以 r 0 = 39 除以 r 1 = 26 得 39 = , 知 r 2 = 13. 最後因為 r 2 = 13 整除 r 1 = 26 知 r 3 = 0, 故由 Theorem 知 gcd(481, 221) = r 2 = 13. 在利用輾轉相除法求最大公因數時, 大家不必真的求到 r n = 0. 例如在上例中可看出 r 0 = 39 和 r 1 = 26 的最大公因數是 13, 利用 Lemma 馬上得知 gcd(a, b) = 13. 在上一節 Corollary 告訴我們若 gcd(a, b) = d, 則存在 m, n Z 使得 d = ma + nb. 當時我們沒有提到如何找到此 m, n. 現在我們利用輾轉相除法來介紹一個找到 m, n 的方法. 我們沿用 Theorem 的符號. 首先看 r 0 = 0 的情形, 此時 d = gcd(a, b) = b 所以若令 m = 0, n = 1, 則我們有 d = b = ma + nb. 當 r 0 0 但 r 1 = 0 時, 我們知 d = gcd(a, b) = r 0. 故利用 a = bh 0 + r 0 知, 若令 m = 1, n = h 0, 則 d = r 0 = ma + nb. 同理若 r 0 = 0, r 1 = 0 但 r 2 = 0, 則知 d = gcd(a, b) = r 1. 故利用 a = bh 0 + r 0 以及 b = r 0 h 1 + r 1 知 r 1 = b r 0 h 1 = b (a bh 0 )h 1 = h 1 a + (1 + h 0 h 1 )b. 因此若令 m = h 1 且 n = 1 + h 0 h 1, 則 d = r 1 = ma + nb. 依照此法, 當 r 0, r 1 和 r 2 皆不為 0 時, 由於 d = gcd(a, b) = r n 1 故由 r n 3 = r n 2 h n 1 + r n 1 知 d = r n 3 h n 1 r n 2. 利用前面推導方式我們知存在 m 1, m 2, n 1, n 2 Z 使得 r n 3 = m 1 a + n 1 b 且 r n 2 = m 2 a + n 2 b 故代入得 d = (m 1 a + n 1 b) h n 1 (m 2 a + n 2 b) = (m 1 h n 1 m 2 )a + (n 1 h n 1 n 2 )b. 因此若令 m = m 1 h n 1 m 2 且 n = n 1 h n 1 n 2, 則 d = ma + nb. 上面的說明看似好像當 r 0 = 0 時對每一個 i {0, 1,..., n 2} 要先將 r i 寫成 r i = m i a+n i b, 最後才可將 d = r n 1 寫成 ma + nb 的形式. 其實這只是論證時的方便, 在實際操作時我們其實是將每個 r i 寫成 m i r i 2 + n i r i 1 的形式慢慢逆推回 d = ma + nb. 請看以下的例子. Example 我們試著利用 Example 所得結果找到 m, n Z 使得 13 = gcd(481, 221) = 481m + 221n. 首先我們有 13 = r 2 = = r 0 r 1. 而 r 1 = = b 5r 0, 故得 13 = r 0 (b 5r 0 ) = 6r 0 b. 再由 r 0 = = a 2b, 得知 13 = 6(a 2b) b = 6a 13b. 故得 m = 6 且 n = 13 會滿足 13 = 481m + 221n. 要注意這裡找到的 m, n 並不會是唯一滿足 d = ma + nb 的一組解. 雖然上面的推演過程好像會只有一組解, 不過只能說是用上面的方法會得到一組解, 並不能擔保可找到所有的

14 1.4. 質數 13 解. 比方說若令 m = m + b, n = n a, 則 m a + n b = (m + b)a + (n a)b = ma + nb = d. 所以 m, n 也會是另一組解. 所以以後當要探討唯一性時, 若沒有充分的理由千萬不能說由前面的推導過程看出是唯一的就斷言是唯一. 一般的作法是假設你有兩組解, 再利用這兩組解所共同滿足的式子找到兩者之間的關係. 我們看看以下的作法. Proposition 假設 a, b N 且 d = gcd(a, b). 若 x = m 0, y = n 0 是 d = ax + by 的一組整數解, 則對任意 t Z, x = m 0 + bt/d, y = n 0 at/d 皆為 d = ax + by 的一組整數解, 而且 d = ax + by 的所有整數解必為 x = m 0 + bt/d, y = n 0 at/d 其中 t Z 這樣的形式. Proof. 假設 x = m, y = n 是 d = ax + by 的一組解. 由於已假設 x = m 0, y = n 0 也是一組解, 故得 am + bn = am 0 + bn 0. 也就是說 a(m m 0 ) = b(n 0 n). 由於 d = gcd(a, b), 我們可以假設 a = a d, b = b d 其中 a, b Z 且 gcd(a, b ) = 1 ( 參見 Corollary 1.2.3). 因此得 a (m m 0 ) = b (n 0 n). 利用 b a (m m 0 ), gcd(a, b ) = 1 以及 Proposition 1.2.7(1) 得 b m m 0. 也就是說存在 t Z 使得 m m 0 = b t. 故知 m = m 0 + b t = m 0 + bt/d. 將 m = m 0 + bt/d 代回 am + bn = am 0 + bn 0 可得 n = n 0 at/d, 因此得證 d = ax + by 的整數解都是 x = m 0 + bt/d, y = n 0 at/d 其中 t Z 這樣的形式. 最後我們僅要確認對任意 t Z, x = m 0 + bt/d, y = n 0 at/d 皆為 d = ax + by 的一組整數解. 然而將 x = m 0 + bt/d, y = n 0 at/d 代入 ax + by 得 a(m 0 + bt/d) + b(n 0 at/d) = am 0 + bn 0 = d, 故得證本定理. 利用 Proposition 我們就可利用 Example 找到 13 = 481x + 221y 的一組整數解 x = 6, y = 13 得到 x = t, y = 13 37t 其中 t Z 是 13 = 481x + 221y 所有的整數解 質數 這一節我們要談整數的分解中最基本的元素 : 質數. 大家都知道一個質數 p 就是正因數只有 1 和本身的數. 我們仍給一個正式的定義. Definition 若 p Z, p > 1 且 p 的正公因數只有 p 和 1 則稱 p 是一個質數 (prime number). 若一正整數有其他的正因數則稱為合成數 (composite number). 簡單來說質數就是無法分解成兩個較小的正整數乘積的數. 質數這一種不可分解的特性讓它有很多特殊性質. 例如給定一質數 p 以及一整數 a Z, 我們很容易判定 gcd(a, p) 為何. 若 d = gcd(a, p) 則因 d p, 知 d = 1 或 d = p. 若 d = p 表示 p a, 所以我們知由 p a, 可得 d = 1. 所以利用 Proposition 1.2.7(1) 我們有以下之結論. Lemma (Euclid). 假設 p 是一個質數, 且 a, b Z. 若 p ab, 則 p a 或 p b. Proof. 這裡我們要證明 p a 或 p b. 如果 p a 當然就可以了 ( 不必擔心是否 p b); 但若 p a, 那麼我們就得證明 p b. 不過由前知 p a 表示 gcd(p, a) = 1, 故利用 Proposition 1.2.7(1) 得證 p b.

15 14 1. 整數的基本性質 Euclid 這一個 Lemma 告訴我們一個質數若是 ab 的因數那它一定是 a, b 其中之ㄧ的因數. 事實上這個性質並不只適用在兩個整數相乘的情況, 我們很容易推廣至更多數相乘之情況. Corollary 假設 p 是一個質數, 且 a 1, a 2,..., a n Z. i {1,..., n} 滿足 p a i. 若 p a 1 a 2 a n, 則存在 Proof. 我們依然用數學歸納法證明. 當 k = 2 時由 Lemma 知若 p a 1 a 2, 則 p a 1 或 p a 2. 假設 k = n 1 時成立, 即若有 n 1 個整數 a 1,..., a n 1 滿足 p a 1 a n 1, 則存在 i {1,..., n 1} 使得 p a i. 現考慮 k = n 的情形, 若 a 1,..., a n 是 n 個整數滿足 p a 1 a n, 則令 a = a 1 a n 1, b = a n. 此時由 p ab 及 Lemma 知 p a 或 p b. 若 p a, 則由數學歸納法假設知存在 i {1,..., n 1} 使得 p a i, 而若 p b 即 p a n, 故得證本定理. 若一質數 p 是一整數 a 的因數, 則我們稱 p 是 a 的一個質因數. 當然了質數 p 本身就是 p 的質因數, 而一個合成數會不會有質因數呢? 大家很自然的覺得一定有, 我們還是給一個正式的證明. Lemma 假設 a Z 且 a > 1. 則必存在一質數 p 使得 p a. Proof. 我們用數學歸納法. 首先若 a = 2, 則由於 2 是質數我們得 p = 2 為所求. 現假設對任意 b Z 滿足 2 b n 的數皆存在質數 p 使得 p b, 我們考慮 a = n + 1 的情形. 若 a 本身是質數那當然 p = a 為所求. 反之, 如果 a 不是質數依定義存在 b Z 且 2 b < a 使得 b a. 故由數學歸納法假設知存在一質數 p 滿足 p b. 因此利用 Proposition 1.1.3(2) 得證 p a. 雖然正整數有無窮多個而 Lemma 告訴我們每一個大於 1 的正整數都有質因數, 但這並不代表會有無窮多個質數. 接著我們就是要探討質數確有無窮多個. 一般來說要證明質數有無窮多個或許會有的想法是希望利用現有的質數創造更大的質數. 不過這個想法是不可行的, 主要的原因是到目前為止我們沒有一個判別一個數是否為質數好的方法. 另類的思考是用反證法, 假設只有有限個質數而得到矛盾. 這個方法就不會碰到判別質數的問題, 相信由此大家更能體會到反證法的妙用. Theorem (Euclid). 質數有無窮多個. Proof. 我們用反證法假設只有有限個質數. 既然只有有限個我們可以將之ㄧ一列出, 就假設 p 1,..., p n 是所有的質數. 現考慮 a = p 1 p n + 1, 由 Lemma 知必有一質數 p i, i {1,..., n} 滿足 p i a. 然而 p i 本身整除 p 1 p n 故由 Corollary 知 p i a p 1 p n, 也就是說 p i 1 而得到矛盾. 故知不可能僅有有限多個質數, 而得證有無窮多個質數. 質數雖然有無窮多個不過他們的分布不是非常稠密的. 例如給定任意大的整數 n 我們可以找到 n 個連續整數都不是質數. 我們的找法是考慮 (n + 1)! + 2, (n + 1)! + 3,..., (n + 1)! + n + 1

16 1.4. 質數 15 這 n 個連續整數. 很容意看出它們都不是質數. 就是質數這麼不容易出現加上很難判別一個很大的數是否為質數, 所以質數常被應用在密碼學中. 底下我們介紹一種最簡單判斷質數的方法. Proposition 若 n > 1 是一整數且對任意小於等於 n 的質數 p 皆不能整除 n, 則 n 為一質數. Proof. 因為我們無法直接證明 n 會是質數, 所以需用反證法. 假設 n 不是質數, 依定義知 存在 a, b Z 滿足 1 < a b < n 且 n = ab. 由此我們可以確定 a n, 否則若 a > n 會造成 ab > ( n) 2 = n 而與 n = ab 不合. 而由 Lemma 知存在質數 p 使得 p a. 既然 p a 我們得 p a n 且 p n. 此與假設所有小於等於 n 的質數皆不整除 n 不符, 故知 n 為質數. Proposition 所提判別質數方法稱為篩法 (sieve method). 它可以幫助我們篩得哪 些數是質數. 例如若要找出所有小於 100 的質數. 我們只要將小於 100 = 10 的質數 ( 即 2, 3, 5, 7) 找出, 留下 2, 3, 5, 7 然後將其餘 2, 3, 5, 7 的倍數刪除, 經過這樣篩選後留下來小於 100 的數就都是小於 100 的質數. 這是因為若 n < 100 且不是質數, 則由 Proposition 知 n 必有一質因數小於等於 n < 100 = 10. 因此被我們所刪除 2, 3, 5, 7 的倍數就是所有小於 100 的合成數, 自然剩下的便都是質數了. 質數既然有無窮多個, 接下來我們可以問是否有些特定形式的質數也會有無窮多個? 例如我們知道偶數中只有 2 是質數, 因此可以將所有奇數分類, 分成 4n + 1 和 4n + 3 這兩類然後問哪一類會有無窮多個質數. 要注意 4n + 1 這一類的數有一重要特性就是兩個 4n + 1 形式的數相乘仍然是 4n + 1 的形式. 因此任意有限多個 4n + 1 形式的數相乘仍是 4n + 1 的形式, 也就是說這一類的數有乘法封閉性. 另一方面 4n + 3 的形式的數就沒有這個特性, 事實上兩個 4n + 3 形式的數相乘會變成 4n + 1 的形式. 利用這兩類數的特性以及類似 Lemma 的證明, 我們有以下之結果. Lemma 假設 a = 4n + 3 其中 n N {0}, 則必存在一質數 p = 4n + 3 其中 n N {0} 滿足 p a. Proof. 我們利用數學歸納法證明. 首先若 a = 3, 則由於 3 是質數我們得 p = 3 為所求. 現假設對任意 b = 4k + 3 Z 滿足 0 k n 1 的數皆存在質數 p = 4k + 3 使得 p b, 我們考慮 k = n 的情形. 若 a 本身是質數那當然 p = a 為所求. 反之, 如果 a 不是質數依定義存在 b, c N 其中 b < a 且 c < a 使得 a = bc. 注意 b, c 中必有一個元素是 4k + 3 形式, 否則 b, c 都是 4k + 1 形式會造成 bc = a 也是 4k + 1 形式的矛盾現象. 就假設 b = 4k + 3 吧! 此時 0 k n 1 ( 因 b < a), 故由歸納假設知存在 p = 4k + 3 使得 p b, 因而得證 p a. 注意 4n + 1 形式的數並不一定有 4n + 1 形式的質因數. 9 就是最簡的的例子. 觀察由 Lemma 推得 Theorem 的關係, 同樣的我們也可利用 Lemma 推得 4n + 3 形式的質數有無窮多個.

17 16 1. 整數的基本性質 Proposition 集合 S = {4n + 3 n Z, n 0} 中有無窮多個質數. Proof. 我們依然用反證法假設 S 中只有有限多個質數並令 p 0 = 3, p 1,..., p n 是 S 中所有的相異質數. 現考慮 a = 4(p 1 p n ) + 3. 由於 a S 利用 Lemma 知必有一質數 p S 滿足 p a, 故由假設知存在 i {0,..., n} 使得 p = p i,. 若 p = p 0 = 3, 則由 3 a, 3 3 以及 a 3 = 4(p 1 p n ) 得知 3 4(p 1 p n ), 故由 Corollary 得到 3 4 或者 3 p i, i {1,..., n} 這樣的矛盾. 若 p = p i 其中 i {1,..., n}, 則由 p i 本身整除 p 1 p n 知 p i a 4(p 1 p n ), 也就是說 p i 3 而得到矛盾. 故得證 S 中不可能僅有有限多個質數. 因為 Lemma 並不適用於 4n + 1 形式的整數, 所以 Proposition 的方法不能用來討論 4n + 1 形式的質數, 不過 4n + 1 形式的質數仍有無窮多個. 事實上數論一個很重要的定理 (Dirichlet Theorem) 告訴我們對任意互質的兩整數 a, b 皆有無窮多個 an + b 形式的質數. 這個定理的證明超出本講義範圍, 我們就不再多談了 算數基本定理 算術基本定理 (The fundamental theorem of arithmetic) 即唯一分解定理, 告訴我們每一個大於 1 的整數若不是質數都可以寫成有限多個質因數的乘積且經過適當排序其寫法唯一. 此定理看似自然且明顯, 但仍需一個正式的證明. 這裡我們又碰到一個典型的有關存在性與唯一性的問題. 這裡的存在性指的就是對一大於 1 的整數可以找到有限多個質數使其可以寫成這些質數的乘積, 而唯一性就是指的就是寫法唯一. 由於正整數和負整數的分解只差一個負號, 我們只需考慮正整數的情況. Theorem (The Fundamental Theorem of Arithmetic). 假設 a N 且 a > 1, 則存在 p 1,..., p r, 其中 p i 是相異的質數, 滿足 n 1 n r a = p p, n i N, i {1,..., r}. 1 r 如果 a 可以分解成另外的形式 a = q 1 m1 q s m s, 其中 q i 是相異的質數, 則 r = s 且經過變換順序可得 p i = q i, n i = m i, i {1,..., r}. Proof. 我們分開來證存在性與唯一性. 首先來看存在性 : 簡單來說存在性就是要證明每一個大於 1 的整數都可以寫成有限多個 ( 可以相同 ) 質數的乘積. 如果 a 本身是個質數, 則 a = p 1 ( 即 r = 1, n 1 = 1), 得證存在性. 如果 a 不是質數呢? 由定義知存在 a 1, b 1 N 且 a 1 1, b 1 1 滿足 a = a 1 b 1. 接下來就是看 a 1, b 1 是不是質數了. 如果其中有一個不是質數, 我們就繼續分解下去直到得到質數為止. 這個過程一定會停下來因為每次分解後得的數越來越小. 當然最後就可以將 a 寫成一些質數的乘積了. 這樣的證明方式, 相信大家會有一種說不清楚的感覺, 所以我們還是用數學歸納法來證明. 當 a = 2 時由於 2 是質數, 所以在這情況存在性是對的. 接著假設對所有從 2 到 a 1 的整數存在性是對的. 如果 a 是質數, 那存在性自然成立. 如果 a

18 1.5. 算數基本定理 17 不是質數, 則知 a = a 1 b 1 其中 a 1, b 1 N 且 1 < a 1 < a 及 1 < b 1 < a. 故利用歸納假設知 a 1 和 b 1 都可寫成有限多個質數的乘積, 所以得證 a 也可以寫成有限多個質數的乘積. 我們依然用歸納法證唯一性, 假設 n 1 n r m 1 m s a = p p = q q, 1 r 1 s 其中 p 1,..., p r 是兩兩相異的質數, 且 q 1,..., q s 也是兩兩相異的質數. 由於 p 1 是質數, 故 m1 由 p 1 a = q 1 qm s s 以及 Corollary 知存在某個 j {1,..., s} 滿足 p 1 q j. 變換一下順序我們可以假設 p 1 q 1. 由於 q 1 是質數, q 1 的因數只能是 ±1 或 ±q 1. 故由 p 1 q 1 知 p 1 = q 1. 現在考慮 a n 1 1 n r m 1 1 m s p 1 1 r 1 s = p p = q q. 由於 a/p 1 < a, 故利用唯一性的歸納法假設我們得 r = s 且 p 1 = q 1,..., p r = q r 以及 n 1 = m 1, n 2 = m 2,..., n r = m r, 故得證唯一性. 一般來說我們將一正整數 a 寫成質數之乘積 a = p n 1 1 p n r 時 r, 為了唯一性我們要求每個質數 p i 的次方 n i 都是正的, 也就是說我們只挑出 a 的質因數 p 1,..., p r. 不過當要討論兩正數 a, b 時為了方便比較, 我們通常會挑出 a 和 b 所有的質因數再將 a, b 寫成這些質數之 n 1 n r m 乘積的樣子. 也就是說可寫成 a = p 1 m r 1 p r 以及 b = p 1 p r 其中對於 i {1,..., r}, p i a 或 p i b, 且 n i 0, m i 0. 注意這裡由於 a 的質因數未必就是 b 的質因數, 反之亦然, 所以 n i, m i 有可能為 0. 這樣寫法的方便性就是我們不必區分哪些 p i 是 a 的質因數, 哪些是 b 的質因數. 利用這樣的寫法我們很容易將 a, b 的最大公因數表示出來. n 1 n 1 m Proposition 假設 a, b N 且 a, b > 1. 若 a = p 1 m r 1 p r 且 b = p 1 p r, 其中 p 1,..., p r 為相異質數且 n i, m i 0, 則 a, b 的正公因數都可寫成 p t 1 1 p t r 的形式 r, 其中 0 t i min{n i, m i }. 特別地, 我們有 min{n 1,m 1 } min{n r,m r} gcd(a, b) = p p. 1 r Proof. 首先回顧一下 min{x, y} 表示 x, y 中最小之數. 現假設 d 是 a, b 的正公因數, 則由 d a 我們知若 p 是 d 的質因數, 則由 p d 知 p a. 故由 Corollary 知存在 i {1,..., r} 使得 p p i. 因此由 p, p i 皆為質數得 p = p i. 也就是說 d 的質因數必在 {p 1,..., p r } 中, 故 d 一定可以寫成 p t 1 1 p t r 的形式 r, 其中 t i 0. 又由於對任意 i {1,..., r} 皆有 p t i i d 故 p t i i a, 亦即 p t i i p n 1 1 n r t p r. 由於若 i = j 則 p = p j, 知此時 gcd(p i i, p n j i j ) = 1, 故由 1.2.7(1) t 得 p i n i p i i, 也就是說 t i n i. 同理由 d b 可得 t i m i, 故得證 0 t i min{n i, m i }. min{n 1,m 1 } min{n 現令 d = p r,m r} 1 p r, 馬上得知 d 為 a, b 之公因數. 又由上知任意 a, b 的公因數 d 皆滿足 d d, 故知 d = gcd(a, b). 雖然 Proposition 也是一個求得兩個數之最大公因數之方法, 不過在實際情況 ( 尤其是處理很大的數時 ) 由於分解質因數是很困難的事情, 所以仍是以輾轉相除法得最大公因數較管用. Proposition 重要之處是它很明確的告訴我們最大公因數長什麼樣子, 這在一些抽象理論的推導是有用的. 接下來我們可以利用 Proposition 將最小公倍數寫下.

19 18 1. 整數的基本性質 n 1 n 1 m Corollary 假設 a, b N 且 a, b > 1. 若 a = p 1 m r 1 p r 且 b = p 1 p r, 其中 p 1,..., p r 為相異質數且 n i, m i 0, 則 Proof. 由於 ab = p n 1 1 +m1 p n r r+mr max{n 1,m 1 } max{n r,m r} lcm(a, b) = p p. 1 r 利用 Proposition 以及 Proposition 知 ab n 1 +m 1 min{n 1,m 1 } n r+m r min{n r,m r} 1 r lcm(a, b) = = p p. gcd(a, b) 對任意二數 x, y, 不失一般性我們假設 x y, 此時我們有 min{x, y} = y 且 max{x, y} = x, 因此得 x + y = min{x, y} + max{x, y}. 所以對任意 i {1,..., r} 我們皆有 max{n i, m i } = n i + m i min{n i, m i }, 因此得證本定理. 當我們有多於兩個的整數時, 我們就可以利用質因數分解以及 Proposition 和 Proposition 將他們的最大公因數和最小公倍數寫下. 例如若 a = p 1 n1 p r n 1, b = m 1 m r t 1 t r p 1 p r 且 c = p 1 p r, 其中 p 1,..., p r 為相異質數且 n i, m i, t i 0, 則 min{n 1,m 1,t 1 } min{n r,m r,t r} gcd(a, b, c) = p p, 1 r max{n 1,m 1,t 1 } max{n r,m r,t r} lcm(a, b, c) = p p. 1 r