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

第3章 唯一質因數分解

本章小節
  1. 3.1 為什麼能分解,以及為什麼結果不變
  2. 3.2 四個例題
  3. 3.3 練習
  4. 3.4 完整解答

3.1 為什麼能分解,以及為什麼結果不變

每個 n>1 都可分解成質數的乘積。用強歸納:若 n 是質數,已經完成;若 n 是合數,寫成 n=ab,且 1<a,b<n。兩個較小數依歸納假設各可分解,合起來就是 n 的分解。這證明存在,還沒有說從不同因子樹會得到一樣的質因數。

唯一性的關鍵是 Euclid 引理:質數 p 若整除 ab,必整除 a 或 b。若 p 不整除 a,gcd(p,a)=1。取 up+va=1,乘 b 得 b=upb+vab;兩項都被 p 整除,所以 p∣b。把引理反覆用於一串質數乘積,左式第一個質數必等於右式某個質數(質數只有自身和 1 是正因數)。配對消去,直到兩側空乘積皆為 1;不能一側還留大於 1 的質因數。這證明除次序外唯一。

常把相同質因數的出現次數寫成指數。對正整數,某數整除另一個數,恰好當每個質數的指數都不超過對方;未出現的指數記 0。取各指數的較小值形成 gcd,取較大值形成最小公倍數 lcm。1 用空乘積表示,負號可獨立提出;0 不用這套分解。

360 分別從 36×10 與 8×45 開始展開,都得到 2³×3²×5。
圖5|360 分別從 36×10 與 8×45 開始展開,都得到 2³×3²×5。

3.2 四個例題

例題1 兩棵樹通向同一組質因數

360=36×10=(6×6)(2×5),把兩個 6 拆成 2×3;也可寫 360=8×45=2³(9×5)。兩路都得到 2³×3²×5。不同是拆法,不是質因數。

例題2 乘積對,還不一定分解完

180=2²×45 是正確的因數乘積,但 45=3²×5 不是質數。繼續拆到每個因子都是質數,才得到 2²×3²×5 的標準形式。

例題3 用指數同時讀出公因數和公倍數

72=2³×3²,120=2³×3×5。各質數取小指數,得 gcd=2³×3=24;取大指數,lcm=2³×3²×5=360。360 除以兩數各得整數,而任何共同倍數都須有這些至少的指數。

72 與 120 按質數 2、3、5 排指數;較小值給 gcd 24,較大值給 lcm 360。
圖6|72 與 120 按質數 2、3、5 排指數;較小值給 gcd 24,較大值給 lcm 360。

例題4 合數不能代入質數引理

6∣2×3,但 6 不整除 2,也不整除 3。證明時需要從 p 不整除 a 推 gcd(p,a)=1;對 6 和 2 這一步就不對。

3.3 練習

  1. B13-C03-Q01 把 84 分解為質數乘積。
  2. B13-C03-Q02 1 和 0 能否像 n>1 一樣列出質因數?
  3. B13-C03-Q03 寫出 −90 的符號與正質因數。
  4. B13-C03-Q04 5³ 整除 2×5²×7 嗎?
  5. B13-C03-Q05 已知 540=2²×3³×5、300=2²×3×5²。求 gcd 與 lcm。
  6. B13-C03-Q06 用指數解釋對正整數 a、b,gcd(a,b)×lcm(a,b)=ab。
  7. B13-C03-Q07 知 7∣a×15,為何推出 7∣a?
  8. B13-C03-Q08 150=2×3×25 算不算唯一質因數分解?
  9. B13-C03-Q09 2³×7² 共有多少個正因數?
  10. B13-C03-Q10 為什麼不能只舉同一數的兩棵因子樹,就算證明唯一性?

3.4 完整解答

Q01

84=4×21=2²×3×7;2、3、7 都是質數。回乘得 4×3×7=84。

Q02

1 對應沒有因子的空乘積;再乘入任何質數就大於 1。0 不能表示為有限個質數的乘積,該乘積至少為 1。

Q03

−90=−1×90,90=2×45=2×3²×5。負號不作質數,質因數來自絕對值。

Q04

不整除。右式的質因數 5 只出現兩次,整除需要至少三次;2、7 不能補出一個 5。

Q05

取小指數得 2²×3×5=60;取大指數得 2²×3³×5²=2700。兩式在每個質數上分別是共同可除與共同倍數的條件。

Q06

若同一質數在兩數中的指數為 i、j,較小值加較大值等於 i+j。每個質數的指數都與 ab 相同,唯一性給出等式。

Q07

7 是質數,而 15 除以 7 餘 1,不能是被 7 整除的因子。由 Euclid 引理,另一個因子 a 必被 7 整除。

Q08

還沒完成,25=5×5。寫成 150=2×3×5²,且三種因子都已是質數,才符合要求。

Q09

因數中的 2 指數可為 0、1、2、3,7 指數可為 0、1、2。任取各一個給不同因數,故有 4×3=12 個(含 1 和原數)。

Q10

有限例子只顯示該數的兩種拆法一致。通用理由是用質數引理在任意兩個分解中找到同一質因數,配對消去,直到沒有因子。