Chapter 13 數論基礎

13.2 質數的定義和性質 13.3 歐幾里得演算法 (Euclidean Algorithm) 13.4 中國餘式定理 (Chinese Remainder Theorem)

13.2 質數的定義和性質

範例一 何謂質數? 有一個正整數 n, n>1 若 n 想寫成二個正整數的乘積只能唯一表示成 n=1n , 範例一 何謂質數? 有一個正整數 n, n>1 若 n 想寫成二個正整數的乘積只能唯一表示成 n=1n , 也就是說除了 n=1n 的表示方式外, 再沒有別的表示方式時, 我們稱 n 為質數. 例如：2 的乘積只能寫成 1 和本身的乘積, 所以 2 是質數 且是最小的質數. 注意！1 並不是質數

範例二 給一個很大的正整數n，如何判定是否為質數? 最蠻力的方法是將 n 除以2，若除得盡，則 n 不為質數。 假若 n 除以2後有非零餘數，則試試將 n 除以3， 若仍除不盡，則再往下試試，將 n 除以5、除以7、…、除以 n1 。 如果 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 ，1ik 後的餘數必為1，這是矛盾的。

範例五 一個質數和下一個質數之間距離有多遠呢? 範例五 一個質數和下一個質數之間距離有多遠呢? 兩個相鄰的質數，其間隔可大到任意大。 只要保證數列中的任一元素皆為合成數， 即可將該相鄰兩質數推開得任意遠。 令該數列=<n!+2, n!+3, …,n!+n> ， 這裡 n 為一任意大的正整數。 很容易可驗證 n!+2 可除盡2；n!+3 可除盡3；…；n!+n 可除盡 n。 以上的可除盡性我們用符號 k|(n!+k)，2kn，表示之。

範例六 任何一個大於1的合成數可表示唯一連串的質數之積(Product)嗎? 可以的! 令C為該合成數，則C可表示為C=pq，1<pq。 針對第一種組合，因為p已是質數，只需將合成數q表示成 q=xy， 然後依照 x 和 y 的質數與合成數之四種組合仿照相同的討論即可。 上表中的第二種組合和第三種組合的討論也類似於第一種組合 之討論。 p q 質數 合成數 

 最大公因數(Greatest Common divisor)，a 和 b 的最大公因數表示成 gcd(a,b) 範例七 對大一點的合成數，可有較好的算數運算式以求得其質數的連 乘積形式? 以長除法求120的質數連乘型式可如下表： 我們得120=2335 120 60 30 15 5 2 3  最大公因數(Greatest Common divisor)，a 和 b 的最大公因數表示成 gcd(a,b)

範例八 證明 f (n)=32n+25n+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。 故得證!

13.3 歐幾里得演算法

最大公因數 假設給兩數 a=120、b=140 a=120=2335 b=140=2257 → gcd(120,140)=20

兩整數 gcd 的歐幾里得演算法即為中學時代所學的輾轉相除法! 上述的輾轉相除法可寫成下列的橫式算術式： 138=524+18 24=118+6 18=36

範例一 如何證明上述輾轉相除法求 gcd(a,b) 的演算法是對的？

範例二 請寫出輾轉相除法的演算法型式 Procedure GCD(a,b) v←a w←b while w0 r←v mod w v←w 範例二 請寫出輾轉相除法的演算法型式 Procedure GCD(a,b) v←a w←b while w0 r←v mod w v←w w←r End 最終的 gcd(a,b)結果存於最後的變數 v 中。

範例三 利用輾轉相除法求 gcd(a,b) 的過程是否可在有限步驟內被完成？

範例四 輾轉相除法的諸多除式中有特殊性質嗎？ 範例四 輾轉相除法的諸多除式中有特殊性質嗎？ …

範例五 輾轉相除法的過程中, 餘數和費氏數列有關係嗎？

範例七 試將 gcd(a,b) 表示成 a 和 b 的線性組合 (Linear Combination) 138=524+18 24=118+6 18=36 得到 6=gcd(138,24) =24118 =24  (138  524) =6 24 138 =6 24 1  138 =( 1) 138+6 24

13.4 中國餘式定理

中國餘式定理的典故為何? 在「孫子算經」中， 今有物不知數 三三數之剩二 五五數之剩三 七七數之剩二 問物幾何？ 上面的描述寫成白話文就 現在有一個不知道的數 將該數除以3，則餘2 將該數除以5，則餘3 將該數除以7，則餘2 試問該數為何？ 如何解出該數。

在上頁投影片中的描述，可否用較數學的形式表達。 解下列三個線性同構式(Linear Congruence): x2(3) x3(5) x2(7) 上式中的3, 5, 7也叫模數(Modulus)， 這裡有一限制，3, 5, 7中任兩數互質

範例一 雖然可將滿足 x=3q1+2 的所有解 {2, 5, 8, 11, 14, 17, 20, 23, …} 中之每一個元素拿出來檢查, 看是否同時也滿足 x=5q2+3 和 x=7q3+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 = 35k1=70。 節點B也可解出X = 21k2=21為其中一解。 節點C也可解出X = 15k3=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，當ij 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=riSibi 所要的通解，其型式如下： 將所求的通解再除以 即得到最小的正整數解，如下所示：

例題4.1 請找出滿足下列線性同餘式的最小整數解： 例題4.1 請找出滿足下列線性同餘式的最小整數解： X  1(3) X  4(5) X  2(7) 根據前面的中國餘式定理，可得到： x  184 (105) 故 x  184 + 105t ,tZ 當t=1時，可得最小正整數解184 105=79