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

第7章 乘法階與週期

本章小節
  1. 7.1 找最短的返回週期,而不是任一週期
  2. 7.2 四個例題
  3. 7.3 練習
  4. 7.4 完整解答

7.1 找最短的返回週期,而不是任一週期

固定 m≥2,且 a 與 m 互質。從 a⁰≡1 開始,逐次乘 a、取餘數,都留在可逆類中。Euler 定理保證第 φ(m) 步會回到 1,因此首次正回返至遲在這一步。最小的正整數 d 使 aᵈ≡1,稱為 a 在模 m 下的乘法階。因為是最小正數,不能把剛好找到的回返指數都叫作階。

若 aʰ≡1 且 h>0,把 h 除以 d,寫成 h=qd+r、0≤r<d。由 aᵈ≡1 知 aʳ≡1,最小性迫使 r=0。所以所有回返指數正是 d 的正倍數,特別有 d∣φ(m)。要證明某候選 d 確是階,除了證明 d 會回來,還須排除其較小的正因數。

已知 a 的階 d 時,aᵏ 的階為 d/gcd(d,k)(k 為正整數)。當 h 為正整數,(aᵏ)ʰ≡1 當且僅當 d∣kh。令 g=gcd(d,k),則 d/g 與 k/g 互質,所以這等價於 d/g∣h。最小的 h 就是 d/g。若 a 不可逆,從 a⁰ 開始的序列仍可能走進循環,但不能有正次方回到 1:那會直接給 a 的反元素。

模 7 依次乘 2,從 1 經 2、4 回到 1;首次正回返在第 3 步。
圖13|模 7 依次乘 2,從 1 經 2、4 回到 1;首次正回返在第 3 步。

7.2 四個例題

例題1 用回到 1 的第一刻定階

模 7 從 1 起乘 2,得到 2、4、8≡1。前兩步不是 1,第三步第一次回來,故階為 3。φ(7)=6 也是一個返回指數,但不是最小。

例題2 只用階就能減少大指數

3 在模 10 的冪依序為 3、9、7、1,階是 4。202=4×50+2,所以 3²⁰²≡3²≡9(mod 10)。不用把餘數 2 誤報成冪值。

例題3 取冪後,階可能變短

2 在模 5 的階是 4,因 2、4、3、1 首次在第四步回返。4≡2²,故 4 的階為 4/gcd(4,2)=2,也可核對 4≢1(mod 5),且 4²=16≡1(mod 5)。

例題4 有循環不表示有乘法階

2 在模 8 不互質。從 1 起冪序列是 1、2、4、0、0、…。0 的循環長度是 1,但沒有正次方同餘 1(mod 8),所以不能稱 2 的乘法階為 1。

模 8 依次乘 2,從 1 經 2、4 到 0,之後停在 0;這不是乘法階。
圖14|模 8 依次乘 2,從 1 經 2、4 到 0,之後停在 0;這不是乘法階。

7.3 練習

  1. B13-C07-Q01 求 3 在模 7 的階。
  2. B13-C07-Q02 已知 2 在模 7 階為 3,求 4 的階。
  3. B13-C07-Q03 用階求 2³⁶ 模 7 的餘數。
  4. B13-C07-Q04 求 2³⁸ 模 7 的餘數。
  5. B13-C07-Q05 求 9 在模 10 的階。
  6. B13-C07-Q06 求 2 在模 9 的階,先用 φ 限制。
  7. B13-C07-Q07 若 a¹²≡1(mod m),其階可能是 7 嗎?
  8. B13-C07-Q08 若 a⁸≡a¹²≡1(mod m),階有何限制?
  9. B13-C07-Q09 求 5 在模 8 的階;它一定等於 φ(8) 嗎?
  10. B13-C07-Q10 為什麼不可逆的 a 不可能有 aᵏ≡1,其中 k>0?

7.4 完整解答

Q01

φ(7)=6,故只需查其正因數 1、2、3、6。前三者的冪餘數為 3、2、6,都不是 1;第 6 次為 1,階是 6。

Q02

因 4=2²,階為 3/gcd(3,2)=3。直接核對 4、2、1 也見第一次在第 3 步。

Q03

36=3×12,是階 3 的倍數,因此餘數 1。

Q04

38=3×12+2,先去掉 12 個完整週期,餘下 2²=4。

Q05

9≢1(mod 10),且 9²≡1(mod 10),故最小正指數是 2。

Q06

φ(9)=6,階只能是 1、2、3、6;2¹、2²、2³ 的餘數為 2、4、8,皆非 1。故階為 6。

Q07

不能。能回到 1 已給出可逆性,階必整除 12,但 7 不整除 12。

Q08

階同時整除 8 和 12,因此整除 gcd(8,12)=4。只由這兩式,可能階為 1、2 或 4。

Q09

5≢1(mod 8),且 5²=25≡1(mod 8),故階為 2。φ(8)=4,只要求階整除 4,並非相等。

Q10

若成立,a·a^(k−1)≡1 就明示 a^(k−1) 是反元素,和不可逆的假設矛盾。