第6章 φ函數與經典同餘定理
6.1 檢查質數、互質與可逆剩餘類
Euler 的 φ(n) 是 1 到 n 中與 n 互質的整數個數(φ(1)=1)。n≥2 時,也就是模 n 有反元素的類數。對質數 p 與正整數 k,模 pᵏ 的標準代表元中恰有 pᵏ⁻¹ 個被 p 整除,所以 φ(pᵏ)=pᵏ−pᵏ⁻¹。兩個互質且大於 1 的模數,其剩餘類由中國剩餘定理一一配對。合併類可逆當且僅當兩邊都可逆,因此 φ(mn)=φ(m)φ(n)(m、n 互質)。若有一個模數為 1,等式由 φ(1)=1 直接成立。依質因數分組就能計算任意正整數的 φ。
若 n≥2 且 gcd(a,n)=1,乘 a 在所有可逆類上是排列,因有反元素,解得回來。把排列前後的類全部相乘:若原乘積為 U,則 a^φ(n)·U≡U(mod n)。U 也可逆,故 a^φ(n)≡1,這是 Euler 定理。取 n=p 為質數且 p∤a,就有 Fermat 小定理 a^(p−1)≡1;乘 a 得 aᵖ≡a。若 p∣a,後一式的兩邊同為 0,所以 aᵖ≡a 對任意整數 a 都成立,前一式仍需檢查 p∤a。
Wilson 定理說,整數 n≥2 是質數當且僅當 (n−1)!≡−1(mod n)。質數 p>2 時,可逆類中互為反元素的配對乘積為 1;自反的類滿足 (x−1)(x+1)≡0,質數整除引理只允許 x≡1、−1。剩下兩者乘出 −1;p=2 直接驗 1!≡−1。若 n 合數,有 1<d<n 的因數,d∣(n−1)!;若又有 n∣((n−1)!+1),d 也整除後者,矛盾。
6.2 四個例題
例題1 用互質條件數可逆類
對 12,只要排除 2 或 3 的倍數。0 至 11 中只剩 1、5、7、11,故 φ(12)=4;並不是 1 到 11 全部有反元素。
例題2 先計各質數冪再相乘
36=4×9,兩因子互質。φ(4)=4−2=2,φ(9)=9−3=6,φ(36)=2×6=12。乘法的條件是兩個模數互質,不能將 φ(36) 當作 φ(6)²。
例題3 大指數先除以可用的週期
7 是質數且 7 不整除 3,故 3⁶≡1(mod 7)。100=6×16+4,所以 3¹⁰⁰≡3⁴=81≡4。這裡只用 6 是一個週期,未說它是最小週期。
例題4 把 6! 按反元素重組
模 7 時,2×4=8≡1,3×5=15≡1。1、6 是自反元素,故 6!≡1×6≡−1。直接驗算 720=7×102+6。
6.3 練習
- B13-C06-Q01 求 φ(18)。
- B13-C06-Q02 求 φ(25)。
- B13-C06-Q03 求 φ(24)。
- B13-C06-Q04 用 Euler 定理求 5¹⁸ 除以 12 的餘數。
- B13-C06-Q05 用 Fermat 小定理判斷 4⁶ 在模 7 的餘數。
- B13-C06-Q06 在模 7 下,7⁷ 是否同餘 7?7⁶ 又能否同餘 1?
- B13-C06-Q07 φ(8)=4,為什麼不能寫 2⁴≡1(mod 8)?
- B13-C06-Q08 用 Wilson 同餘核對 5 的情形。
- B13-C06-Q09 不必算出 8!,為什麼 n=9 不會符合 Wilson 同餘?
- B13-C06-Q10 p=2 時,自反的 1 和 −1 是不同類嗎?Wilson 是否仍成立?
6.4 完整解答
Q01
18=2×9,兩因子互質,φ(18)=(2−1)(9−3)=6。
Q02
25=5²,恰有 5 個被 5 整除的代表,故 φ(25)=25−5=20。
Q03
24=8×3 且互質;φ(8)=8−4=4、φ(3)=3−1=2,乘得 8。
Q04
5 與 12 互質,φ(12)=4。18=4×4+2,故同餘 5²=25,其非負餘數為 1。
Q05
7 為質數,且不整除 4;p−1=6,所以餘數是 1。
Q06
7⁷ 和 7 都是 7 的倍數,所以同餘 0。7⁶ 也同餘 0,不同餘 1;帶 p−1 的式子不適用於這個底數。
Q07
2 與 8 不互質。直接算 2⁴=16≡0,不是 1,顯示少掉可逆條件就不能取消乘積。
Q08
(5−1)!=4!=24=5×4+4,餘數 4 即 −1 的代表,符合質數情形。
Q09
8! 含因子 3 與 6,乘積被 9 整除,所以 8!≡0(mod 9),並非 −1。
Q10
不是不同類,因 1−(−1)=2。直接算 (2−1)!=1≡−1(mod 2),仍成立,不能搬用兩個不同自反類的計數。