第十三冊 v0.2 · 網站閱讀版

第2章 Euclid算法與最大公因數

本章小節
  1. 2.1 每次換一對數,公因數不變
  2. 2.2 四個例題
  3. 2.3 練習
  4. 2.4 完整解答

2.1 每次換一對數,公因數不變

不全為零的整數 a、b 的最大公因數記作 gcd(a,b),取正數;符號可先取絕對值。若其中一個是 0,gcd 就是另一個的絕對值;本冊不把 gcd(0,0) 當作求正最大值的問題。gcd=1 稱互質,並不要求兩個數各自為質數。

若 b>0 且 a=bq+r,a、b 的公因數也整除 r=a−bq;反過來,b、r 的公因數整除 a=bq+r。兩對數的公因數集合完全相同,故 gcd(a,b)=gcd(b,r)。把正餘數反覆當除數,它們嚴格下降,終會到餘數 0。最後一個非零除數是 gcd;原來的每個公因數都整除這個值。

將每次餘數寫成上一對的整數線性組合,從最後一個非零除數向上代回,得到 gcd(a,b)=ua+vb,u、v 為整數,稱為 Bézout 等式。若第一步餘數已是 0,最後非零除數就是 |b|,直接用 b 的正負號寫出係數。若 b=0,則由 |a| 寫出。反過來,若有 ua+vb=1,任何公因數都整除 1,所以 a、b 互質。這給下一章的質數引理和求模反元素一個可驗算的工具。

252、105 依次換成 105、42,再換成 42、21 及 21、0;最大公因數仍為 21。
圖3|252、105 依次換成 105、42,再換成 42、21 及 21、0;最大公因數仍為 21。

2.2 四個例題

例題1 輾轉相除與逆向代回

252=2×105+42,105=2×42+21,42=2×21+0,所以 gcd=21。從 21=105−2×42,代入 42=252−2×105,得 21=5×105−2×252。直接相乘相減,也能驗算等式。

由 21=105−2×42、42=252−2×105,回代得 21=5×105−2×252。
圖4|由 21=105−2×42、42=252−2×105,回代得 21=5×105−2×252。

例題2 互質也能交出線性組合

35=22+13、22=13+9、13=9+4、9=2×4+1。從 1=9−2×4=3×9−2×13,再用 9=22−13、13=35−22,得 1=8×22−5×35。35 與 22 互質。

例題3 負號要回填到原式

先算 24=18+6、18=3×6,所以 gcd(−24,18)=6。將 6=24−18 改寫成 6=(−1)(−24)−18,才是對原輸入的整數線性組合。

例題4 相鄰兩數不必實際相除

任兩個相鄰整數 k 和 k+1 的差是 1。任何可同時整除它們的正數都整除 1,所以 gcd=1,包括 k=−1 或 0 的情形。

2.3 練習

  1. B13-C02-Q01 用 Euclid 算法求 gcd(84,30)。
  2. B13-C02-Q02 將上一題的 6 寫成 84 與 30 的整數線性組合。
  3. B13-C02-Q03 gcd(0,−18) 是多少?
  4. B13-C02-Q04 為什麼這裡不取 gcd(0,0) 的正最大值?
  5. B13-C02-Q05 求 gcd(91,65)。
  6. B13-C02-Q06 求 gcd(81,57),列出正餘數。
  7. B13-C02-Q07 用例題 2 的等式找 22x+35y=5 的一組解。
  8. B13-C02-Q08 算 gcd(−21,14),並給原輸入的線性組合。
  9. B13-C02-Q09 用線性組合驗證 9 與 14 互質。
  10. B13-C02-Q10 gcd(8,12)=4。兩數同乘 4 後,為什麼 gcd(32,48)=16?

2.4 完整解答

Q01

84=2×30+24,30=24+6,24=4×6,最後非零餘數 6。因此 gcd 是 6。

Q02

6=30−24;把 24 改成 84−2×30,得到 6=3×30−84,可直接代回。

Q03

0 被每個非零整數整除,共同正因數只需是 18 的正因數,最大者 18。

Q04

每個正整數都同時整除兩個 0,集合沒有最大者。若其他約定將 gcd(0,0) 定為 0,是延伸定義,不是這裡求正最大值的結果。

Q05

91=65+26,65=2×26+13,26=2×13。因此 gcd=13。

Q06

81−57=24,57−2×24=9,24−2×9=6,9−6=3,此後 6 除以 3 餘 0。序列 24、9、6、3 下降,gcd=3。

Q07

1=8×22−5×35,等式乘 5 得 5=40×22−25×35,所以可取 x=40、y=−25。

Q08

21=14+7,14=2×7,所以 gcd=7。將 21−14 寫成 (−1)(−21)−14 就是要的組合。

Q09

2×14−3×9=1。任何共同正因數都整除這個 1,因此互質。

Q10

可直接作 48=32+16、32=2×16。一般輾轉相除時,同乘正整數會把每個餘數也同乘該數,商不變。