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

第4章 模同餘與模反元素

本章小節
  1. 4.1 同餘是同一類,不是原數相等
  2. 4.2 四個例題
  3. 4.3 練習
  4. 4.4 完整解答

4.1 同餘是同一類,不是原數相等

固定正模數 m≥2。若 m∣(a−b),記 a≡b(mod m),即 a、b 除以 m 的非負餘數相同。代表元不必在 0 到 m−1,但每類恰有一個在這個標準範圍。相差任何整數倍的 m 都仍是同一類。

在同一模數下,可把同餘式相加、相減、相乘。乘法的理由是若 a≡c 且 b≡d,則 ab−cd=(a−c)b+c(b−d),兩項都被 m 整除。先減小代表元,再運算再取餘數,結果不受選哪個代表元影響。

若 au≡1(mod m),u 是 a 的模反元素。寫成 au+vm=1 的整數形式,就是互質的 Bézout 等式,因此存在反元素恰等於 gcd(a,m)=1。若 au≡av≡1,把 au≡av 的兩邊乘 u,利用 ua≡1 得 u≡v。在 ax≡ay 中,只有已知 a 在此模數下可逆,才可直接乘反元素消去 a;不可以照普通分數消去。

模 6 的標準代表元依次為 0 到 5。−14 與 4 差 −18,落在同一類。
圖7|模 6 的標準代表元依次為 0 到 5。−14 與 4 差 −18,落在同一類。

4.2 四個例題

例題1 用非負餘數定位負代表元

−14=6(−3)+4,所以 −14≡4(mod 6)。4−6=−2 也代表同一類,但標準代表元是 4,因為 0≤4<6。

例題2 由線性組合找到反元素

26=3×7+5,7=5+2,5=2×2+1。回代得 1=3×26−11×7,故 7 的反元素是 −11≡15(mod 26)。驗算 7×15=105=4×26+1。

例題3 合併了兩類便不能原路返回

模 6 下,2×1=2、2×4=8,兩者同餘。但 1−4=−3 不被 6 整除。乘 2 的映射將不同類合在同一類,因 gcd(2,6)=2,沒有可用的反元素。

模 6 的各類乘 2 得 0、2、4、0、2、4;1 與 4 都映到 2,不能逆推原類相同。
圖8|模 6 的各類乘 2 得 0、2、4、0、2、4;1 與 4 都映到 2,不能逆推原類相同。

例題4 先取餘數再平方

37 除以 8 餘 5,因此 37²≡5²=25≡1(mod 8)。只需平方較小的整數代表元 5。

4.3 練習

  1. B13-C04-Q01 −23 在模 7 的標準代表元是多少?
  2. B13-C04-Q02 41 與 6 在模 7 下同餘嗎?
  3. B13-C04-Q03 用小代表元求 19+23 與 19×23 除以 6 的餘數。
  4. B13-C04-Q04 找 5 在模 12 下的反元素。
  5. B13-C04-Q05 6 在模 15 有反元素嗎?
  6. B13-C04-Q06 找 −3 在模 7 下的標準反元素。
  7. B13-C04-Q07 指出 2×1≡2×4(mod 6)不推出哪句話。
  8. B13-C04-Q08 若 3x≡3y(mod 8),為什麼能消去 3?
  9. B13-C04-Q09 寫出所有滿足 x≡−2(mod 5)的整數。
  10. B13-C04-Q10 用代表元解釋奇數的平方模 8 為何都是 1。

4.4 完整解答

Q01

−23=7(−4)+5,標準範圍為 0 到 6,所以是 5。

Q02

41−6=35=7×5,因此同餘。原整數不同,並不妨礙代表同一類。

Q03

19≡1、23≡5。和同餘 1+5=6,即 0;積同餘 1×5=5。

Q04

5×5=25=2×12+1,直接驗出 5 是自己的反元素。

Q05

gcd(6,15)=3≠1。每個 6u+15v 都被 3 整除,不可能等於 1,所以無反元素。

Q06

(−3)×2=−6=−7+1,所以 2 就是反元素,且在標準範圍。

Q07

它不推出 1≡4(mod 6),因差 −3 不被 6 整除。消去因子 2 需要模 6 的反元素,而 2 沒有。

Q08

3×3=9≡1(mod 8),故兩側乘 3 得 x≡y。這裡消去是經由反元素,不靠除法。

Q09

因 −2≡3,解為 x=3+5t,其中 t 為任意整數;每一個都與 3 相差 5 的倍數。

Q10

奇數只可能同餘 1、3、5、7。四個平方為 1、9、25、49,都與 1 相差 8 的倍數。