第九章 數論基礎
9.2 質數的定義和性質 9.3 歐幾里得演算法 (Euclidean Algorithm) 9.4 中國餘式定理 (Chinese Remainder Theorem)
9.2 質數的定義和性質 本小節須學好下列重點: 質數的判別與性質 質數與合成數的關係
範例一 何謂質數? 有一個正整數 n, n>1 若 n 想寫成二個正整數的乘積只能唯一表示成 n=1n , 範例一 何謂質數? 有一個正整數 n, n>1 若 n 想寫成二個正整數的乘積只能唯一表示成 n=1n , 也就是說除了 n=1n 的表示方式外, 再沒有別的表示方式時, 我們稱 n 為質數. 例如:2 的乘積只能寫成 1 和本身的乘積, 所以 2 是質數 且是最小的質數. 注意!1 並不是質數
範例二 給一個很大的正整數n,如何判定是否為質數? 最蠻力的方法是將 n 除以2,若除得盡,則 n 不為質數。 假若 n 除以2後有非零餘數,則試試將 n 除以3, 若仍除不盡,則再往下試試,將 n 除以5、除以7、…、除以 n1 。 如果 n 除以這些數皆有非零餘數,則 n 必為質數。
範例三 是否有比 O(n) 更快的質數判定法? 有的! 令 n=61,則61除以2、3、5和7皆得非零的餘數, 那麼61並不需要除以11以判定其是否為質數, 原因是61=5×11+6,那意謂著61=11×5+6。 這隱含著61除以5有非零餘數時,也等同於61除以11有非零餘數。 不難感覺出判定 n 是否為質數,只需檢查2、3、5…和 是否可被 n 除盡即可。 最壞情況需花 的時間即可判定 n 是否為質數。 此種質數判定法也稱 埃拉托森(Eratosthenes)篩洗法
範例四 質數的個數是否為有限個? 利用反證法(By Contradiction) 範例四 質數的個數是否為有限個? 利用反證法(By Contradiction) 假設質數的個數為有限個,令這k個質數為P1 、P2 、P3 …和 Pk。 因為數列 P 中已包含了所有的質數,所以任何一個不在數列 P 內 的數必為合成數。我們現在找出一個合成數,其型式為 很容易可檢查出該合成數 C 必大於假設中的最大質數 且該合成數 C 除以任一個 Pi ,1ik 後的餘數必為1,這是矛盾的。
範例五 一個質數和下一個質數之間距離有多遠呢? 範例五 一個質數和下一個質數之間距離有多遠呢? 兩個相鄰的質數,其間隔可大到任意大。 只要保證數列中的任一元素皆為合成數, 即可將該相鄰兩質數推開得任意遠。 令該數列=<n!+2, n!+3, …,n!+n> , 這裡 n 為一任意大的正整數。 很容易可驗證 n!+2 可除盡2;n!+3 可除盡3;…;n!+n 可除盡 n。 以上的可除盡性我們用符號 k|(n!+k),2kn,表示之。
範例六 任何一個大於1的合成數可表示唯一連串的質數之積(Product)嗎? 可以的! 令C為該合成數,則C可表示為C=pq,1<pq。 針對第一種組合,因為p已是質數,只需將合成數q表示成 q=xy, 然後依照 x 和 y 的質數與合成數之四種組合仿照相同的討論即可。 上表中的第二種組合和第三種組合的討論也類似於第一種組合 之討論。 p q 質數 合成數
最大公因數(Greatest Common divisor),a 和 b 的最大公因數表示成 gcd(a,b) 範例七 對大一點的合成數,可有較好的算數運算式以求得其質數的連 乘積形式? 以長除法求120的質數連乘型式可如下表: 我們得120=2335 120 60 30 15 5 2 3 最大公因數(Greatest Common divisor),a 和 b 的最大公因數表示成 gcd(a,b)
範例八 證明 f (n)=32n+25n+1為4的倍數,其中n為非負整數 其中 t, p Ζ,故得證
範例九 令 S={2, 16, 128, 1024, 8192, 65536},若從S中取四個數來, 證明其中必有兩數的乘積為131072。 令S1={2, 65536}、S2={16, 8192}、S3={128, 1024}, 則在S中取四數, 根據鴿籠原理可知必有一集合Si中的兩數皆被取得, 其中i{1, 2, 3},而此兩數乘積為131072。 故得證!
9.3 歐幾里得演算法 本小節須學好下列重點: 最大公因數的求法 輾轉相除法的應用
最大公因數 假設給兩數 a=120、b=140 a=120=2335 b=140=2257 → gcd(120,140)=20
兩整數 gcd 的歐幾里得演算法即為中學時代所學的輾轉相除法! 上述的輾轉相除法可寫成下列的橫式算術式: 138=524+18 24=118+6 18=36
範例一 如何證明上述輾轉相除法求 gcd(a,b) 的演算法是對的?
範例二 請寫出輾轉相除法的演算法型式 Procedure GCD(a,b) v←a w←b while w0 r←v mod w v←w 範例二 請寫出輾轉相除法的演算法型式 Procedure GCD(a,b) v←a w←b while w0 r←v mod w v←w w←r End 最終的 gcd(a,b)結果存於最後的變數 v 中。
範例三 利用輾轉相除法求 gcd(a,b) 的過程是否可在有限步驟內被完成?
範例四 輾轉相除法的諸多除式中有特殊性質嗎? 範例四 輾轉相除法的諸多除式中有特殊性質嗎? …
範例五 輾轉相除法的過程中, 餘數和費氏數列有關係嗎?
範例七 試將 gcd(a,b) 表示成 a 和 b 的線性組合 (Linear Combination) 138=524+18 24=118+6 18=36 得到 6=gcd(138,24) =24118 =24 (138 524) =6 24 138 =6 24 1 138 =( 1) 138+6 24
9.4 中國餘式定理 本小節須學好下列重點: 何謂中國餘式定理及其典故 中國餘式定理的使用方法
中國餘式定理的典故為何? 在「孫子算經」中, 今有物不知數 三三數之剩二 五五數之剩三 七七數之剩二 問物幾何? 上面的描述寫成白話文就 現在有一個不知道的數 將該數除以3,則餘2 將該數除以5,則餘3 將該數除以7,則餘2 試問該數為何? 如何解出該數。
在上頁投影片中的描述,可否用較數學的形式表達。 解下列三個線性同構式(Linear Congruence): x2(3) x3(5) x2(7) 上式中的3, 5, 7也叫模數(Modulus), 這裡有一限制,3, 5, 7中任兩數互質
範例一 雖然可將滿足 x=3q1+2 的所有解 {2, 5, 8, 11, 14, 17, 20, 23, …} 中之每一個元素拿出來檢查, 看是否同時也滿足 x=5q2+3 和 x=7q3+2 , 但這太沒效率了. 是否有更快的方法? X 1(3) X 0(5) X 0(7) X 0(3) X 1(5) X 0(7) X 0(3) X 0(5) X 1(7) A B C 圖6.4.1 中國餘式定理的分割示意圖
從節點A中的三個特殊線性同構式:X 1(3)、X 0(5)、X 0(7), 不難解出 X = 35k1=70。 節點B也可解出X = 21k2=21為其中一解。 節點C也可解出X = 15k3=15為其中一解。 將節點A的 X 1(3) 調整回 X 2(3),X=70 需要修改成 X=140。 同樣的道理,對節點B而言,X=63,而對節點C而言,X=30。 這就是「演算法統宗」所說: 三人同行七十稀 五樹梅花廿一枝 七子團圓整半月 除百零五便得知
“三人同行七十稀”指的是滿足 X 1(3) 、 X 0(5) 和 X 0(7) 三個線性同餘式的解為70。 “五樹梅花廿一枝”的廿一枝指的是滿足 X 0(3) 、 X 1(5) 和 X 0(7) 的解21。 “七子團圓整半月”的整半月指的是滿足 X 0(3) 、 X 0(5) 和 X 1(7) 的解15。 令 x=140+63+30=223,很容易可檢定出 x 滿足最原始的三個線性同餘 式。其實 x=223+105k 即為通解。 當 k=2時,x=23 為得到的最小整數解。 所謂的“除百零五便得知”,指的就是將233除以105得到 x=23的 最後解。
範例四 範例三的解答似乎是針對特殊的三個線性同構式, 範例四 範例三的解答似乎是針對特殊的三個線性同構式, 可否給一個較一般的通解 假設有m個線性同構式如下所示: x r1(P1) x r2(P2) x rm(Pm) (6.4.2) 這裡 gcd(Pi,Pj)=1,當ij x 0(P1) x 0(P2) x 1(Pi) x 0(Pm) (6.4.3) … … …
滿足式(6.4.3)所述m個同構式的解之形式為: (6.4.4) 式(6.4.4)中的bi可用嘗試法求得,將式(6.4.3)中的第 i 個式子調整回 x ri(Pi) 則滿足調整後的 個同餘式之解為: x=riSibi 所要的通解,其型式如下: 將所求的通解再除以 即得到最小的正整數解,如下所示:
例題4.1 請找出滿足下列線性同餘式的最小整數解: 例題4.1 請找出滿足下列線性同餘式的最小整數解: X 1(3) X 4(5) X 2(7) 根據前面的中國餘式定理,可得到: x 184 (105) 故 x 184 + 105t ,tZ 當t=1時,可得最小正整數解184 105=79