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

第9章 p進賦值與Möbius反演

本章小節
  1. 9.1 一邊數質因數,一邊沿因數格拆回原值
  2. 9.2 四個例題
  3. 9.3 練習
  4. 9.4 完整解答

9.1 一邊數質因數,一邊沿因數格拆回原值

固定質數 p。對非零整數 a,vₚ(a) 是 |a| 的質因數 p 的指數,也就是 pᵏ∣a 的最大非負整數 k。由唯一分解,非零整數 a、b 滿足 vₚ(ab)=vₚ(a)+vₚ(b)。a、b 與 a+b 都非零時,提出較低次的共同因子 pᵏ,得 vₚ(a+b)≥較小的賦值;兩賦值不同時,括號內一項不被 p 整除、另一項被 p 整除,因此恰好相等。若兩者同次,括號可能再多出 p 因子;不能把加法當乘法。

Möbius 函數 μ(n) 用於正整數:μ(1)=1;若某個質數平方整除 n,μ(n)=0;其餘若有 r 個相異質因數,μ(n)=(−1)ʳ。將 μ(d) 對 n 的正因數 d 加總,只有不含平方的因數有貢獻。它們由 n 的相異質數任選子集給出,故 n>1 時正負抵消,總和 0;n=1 時總和 1。

若 g(n)=Σ f(d)(對所有正因數 d∣n 加總),要回推出 f(n),可算 Σ μ(d)g(n/d),仍對同一批因數 d 加總。展開 g 後,一個 f(e)(e∣n)出現的條件是 de∣n,係數就是對 n/e 的所有因數加總 μ。除 e=n 時係數為 1 外,其他全抵消,所以結果是 f(n)。這是有限因數和的反演,不需要談無限級數或收斂。

40 連除 2 得 20、10、5,第一次到不再能除的 5,已除三次,所以 v₂(40)=3。
圖17|40 連除 2 得 20、10、5,第一次到不再能除的 5,已除三次,所以 v₂(40)=3。

9.2 四個例題

例題1 用乘法累加指數

40=2³×5,12=2²×3,故 v₂(40×12)=3+2=5。回算 480=2⁵×15,15 是奇數,沒有漏掉另一個 2。

例題2 加法須看兩邊指數是否相等

40 與 12 的 2 賦值分別 3、2,52=2²×13,指數為較小的 2。若改把 40 與 56 相加,兩個指數都為 3,96=2⁵×3,提升到 5。

例題3 先看平方因數,再決定正負

12 的因數是 1、2、3、4、6、12。4 與 12 都含 2²,μ=0;2、3 各有一個質因數,μ=−1;6 有兩個,μ=1。連同 μ(1)=1,加總 1−1−1+0+1+0=0。

12 的正因數 1、2、3、4、6、12 的 μ 值為 1、−1、−1、0、1、0,總和是 0。
圖18|12 的正因數 1、2、3、4、6、12 的 μ 值為 1、−1、−1、0、1、0,總和是 0。

例題4 用反演把總和拆開

若 g(n) 是所有正因數的和,也就是 f(d)=d。取 n=12,g(12)=28、g(6)=12、g(4)=7、g(2)=3;μ(4)=μ(12)=0,不用其對應項。反演為 28−12−7+3=12,正好取回 f(12)。

9.3 練習

  1. B13-C09-Q01 求 v₃(54)。
  2. B13-C09-Q02 求 v₂(−72),負號影響它嗎?
  3. B13-C09-Q03 求 v₅(125×20)。
  4. B13-C09-Q04 求 v₃(18+27),不用先做質因數分解。
  5. B13-C09-Q05 求 v₂(12+20)。為何不能直接取較小指數?
  6. B13-C09-Q06 算 μ(30)、μ(18)。
  7. B13-C09-Q07 算 μ(1)、μ(12),各用哪個條件?
  8. B13-C09-Q08 列出 d∣6 的 μ(d) 並求和。
  9. B13-C09-Q09 若 g(n)=Σ f(d)(對 n 的正因數 d 加總),且 g(n) 為 n 的正因數個數,用反演算 f(6)。
  10. B13-C09-Q10 能否把質數 p 改為 4,仍保證用最大 k 的指數在乘法下相加?

9.4 完整解答

Q01

54=2×27=2×3³,因子 2 不再被 3 整除,故值為 3。

Q02

取絕對值 72=2³×9,9 為奇數,所以值是 3。負號不增加任何 2 因子。

Q03

125=5³、20=5×4,兩指數分別 3、1。相乘相加得 4。

Q04

v₃(18)=2、v₃(27)=3,指數不同,提出 3² 後括號為 2+3,不被 3 整除,故值 2。

Q05

兩項都是 v₂=2。提出 4,括號是 3+5=8,還有三個 2,故結果 2+3=5。

Q06

30=2×3×5 不含平方,三個相異質數給 (−1)³=−1。18=2×3² 含平方,所以為 0。

Q07

1 是空乘積,特別取 1;12 含質數平方 2²,取 0。不能把 1 當作有一個質因數。

Q08

因數 1、2、3、6 的值依序 1、−1、−1、1,加總 0,符合 6>1 的抵消。

Q09

6 的因數 1、2、3、6 給 g(6)−g(3)−g(2)+g(1)=4−2−2+1=1。原本正好是把每個因數的 1 加起來。

Q10

不能。2 中最大的 4 指數為 0,但 2×2=4 的指數為 1,不是 0+0。這不是本章的質數賦值。