動機
為甚麼要超越歐拉定理?
歐拉(Euler)定理說,只要 ,就有 。指數 總是可用,但往往遠大於對所有單位同時成立的最小指數。模 的單位為 ,它們的平方都是 ;儘管 ,指數 已經足夠。我們還會看到,模 的每個單位都滿足 ,但 。
於是自然要問:使每個單位都滿足 的最小正整數 是多少?答案是 Carmichael 函數 。它還可用於研究另一個問題:費馬(Fermat)小定理說明質數 對每個與 互質的底數滿足 ;哪些合數 對每個與 互質的底數都滿足 ?瞭解 後,Korselt 判據將給出答案。
以下均設 。記 為模 與 互質的剩餘類構成的乘法群,故 。對單位 , 是它在 中的階。我們使用有限群的基本事實: 當且僅當 。
通用指數
定義 3.2.1
(通用指數與 Carmichael 函數)
設 。若正整數 滿足
則稱 為模 的通用指數。由歐拉定理, 是通用指數,故這樣的指數存在。Carmichael 函數 是其中最小的正整數。
定理 3.2.2
(通用指數的結構)
設 是 遍歷 時所有 的最小公倍數,則:
- 正整數 為通用指數當且僅當 ;
- ;
- 為通用指數當且僅當 ;特別地,。
證明
(階與它們的最小公倍數)
是通用指數當且僅當每個單位 均滿足 ,亦即每個 。有限個正整數都整除 ,當且僅當它們的最小公倍數 整除 ,得到 (1)。因此通用指數恰是 的正倍數,其最小值為 ,得到 (2),並由此得到 (3)。歐拉定理使 成為通用指數,故 。
這裏關鍵是整除性:僅憑最小性只能得到 。結構定理還說明每個對所有單位有效的指數都是最小指數的倍數。
只討論單位。 定義僅量化單位,不能推廣到非單位。若 ,則任何 都不可能滿足 :否則 同時整除 和 ,便會整除 。例如 只會是 或 ,從不是 。
用中國剩餘定理分解模數
定理 3.2.3
(最小公倍數公式)
若 且 ,則
因此若 ,其中 兩兩不同,則
證明
(互質因子的通用指數)
寫 。我們證明 是模 的通用指數,當且僅當它同時是模 的通用指數。
先設 對模 通用,任取模 的單位 。中國剩餘定理給出整數 ,使
於是 分別與 互質,故與 互質。由 ,模 約化得 。對 同理。
反之,若 對兩個模數都通用,且 ,則 都整除 。它們互質,所以乘積 也整除 。
由結構定理,這些通用指數恰是同時被 整除的正整數,其最小值為兩者最小公倍數。對質數冪個數 歸納即可得到一般公式:各質數冪兩兩互質,最小公倍數滿足結合律。
計算因而歸結為質數冪。奇質數冪與 的冪表現不同,必須分開處理。
奇質數冪
定理 3.2.4
(奇質數冪)
若 為奇質數,,則 。
證明
(生成元的階為 )
使用先前建立的奇質數冪原根定理: 是循環群。取生成元 ,則 。結構定理表明 是每個單位的階的倍數,故 ;結構定理還給出反向整除,因此二者相等。
特別地, 給出 。
2 的冪
定理 3.2.5
(2 的冪)
證明
(以平方得上界,以單位 得下界)
小指數情形。 ,故 。,且 、,故 ,。
的上界。 對 歸納,證明每個奇數 都滿足
當 ,寫 ,則 ; 為偶數,故 。若 ,平方得
因為 ,右邊模 同餘於 ,即為 的結論。所以 是模 的通用指數,結構定理給出 。
的精確階。 我們證明每個 都有
亦即 ;這裏 是質因數分解中 的指數。 時 。若結論對 成立,則二項式定理給出
括號內是奇數加偶數,仍為奇數,歸納完成。
固定 。由上界, 整除 ,故為某個 ,。若 ,則 ,即 。但上面的結論取 給出賦值恰為 ,矛盾。因此 。
是 的階的倍數,又整除 ,故兩者相等。
證明透視
2 的冪的論證結構
- 上界: 平方把誤差項 變為 ,因此模數翻倍時所用指數也翻倍。
- 下界: 一個具有足夠大階的具體單位就足夠; 是直接由二項式定理證明的,沒有調用未說明的提升引理。
- 為何要求 : 基礎情形使用 。 時公式給出 ,但 ; 時公式甚至不是整數。
與 的差距在 時已經出現。
反例模式
$\lambda(8)$ 嚴格小於 $\varphi(8)$
模 , 的平方分別為 ,都同餘於 。由於 ,指數 無效,故 ,但 。
因此模 沒有階為 的單位, 不是循環群。更一般地,對 ,,所以模 沒有原根;奇質數冪的原根定理不能直接用於這些模數。
指數 對非單位並不適用:模 ,、、。
例題 3.2.6
(計算 )
。由最小公倍數公式及兩條質數冪定理,
而 。因此每個模 的單位滿足 。抽查:,。 整除 ,商為 。
概念視角結構
Carmichael 函數是群的指數
用群的語言說, 是有限阿貝爾(Abel)群 的指數,即其所有元素階的最小公倍數。在阿貝爾群中,這個最小公倍數總能取到:若可交換的兩個元素的階 互質,它們的積的階就是 ;對每個質數,取階中含該質數最高冪的元素並把它們組合,便得到一個階恰為 的單位。所以 是循環群,當且僅當 ; 時這不成立。
Carmichael 數
定義 3.2.7
(Carmichael 數)
Carmichael 數是滿足下列條件的合數 :對每個滿足 的整數 ,
由結構定理,定義條件恰好說 是模 的通用指數。因此合數 是 Carmichael 數當且僅當 。
邊界情形。 定義排除質數。例如 依費馬小定理對每個單位滿足同餘,但它不是合數。最小合數 不滿足:;具體地,。
定理 3.2.8
(Korselt 判據)
合數 是 Carmichael 數,當且僅當:
- 無平方因子;
- 對每個整除 的質數 ,有 。
證明
(以兩個見證元證明必要性,以最小公倍數公式證明充分性)
必要性:無平方因子。 設 為 Carmichael 數,假設某個質數 滿足 。寫 ,其中 、。由中國剩餘定理取 滿足
若 ,取 。由於 且 ,有 ,因而 。
由 ,在模 下有 。對 ,二項式定理給出
取 ,得到 ,所以 。但 ,於是 ,矛盾。該論證對 也成立。
必要性:整除條件。 設 ,寫 ,其中 。若 ,則 整除任何整數;故設 為奇數。由原根定理 的情形,存在模 的原根 ,即 。因 ,它也是模 的單位。由中國剩餘定理取
於是 ,故 。模 約化得 ,因此 。
充分性。 設合數 無平方因子,寫為不同質數之積 ,且每個 。奇質數冪定理給出奇質數的 ,2 的冪定理給出 。由最小公倍數公式,
每個 都整除 ,故其最小公倍數也整除 。於是 , 是通用指數, 是 Carmichael 數。
證明透視
各假設如何出現
- 無平方因子: 單位 的冪模 形如 。若指數 使它同餘於 ,便要求 ,這與 矛盾。
- : 模 的原根的階恰為 ;中國剩餘定理將它嵌入模 的單位,同時控制其他質因子。
- 充分性: 無平方因子時, 是各 的最小公倍數;假設恰好要求這些數都整除 。
例題 3.2.9
(561 是 Carmichael 數)
是無平方因子的合數,。逐一檢查:
由 Korselt 判據, 是 Carmichael 數。也可計算 ,且 。
歐拉定理本身不能解釋這個結論: 不整除 ;整除 的是較小的指數 。
例題 3.2.10
(341 通過底數 2,卻不是 Carmichael 數)
無平方因子。由於 ,有 ,底數 不能檢出 為合數。
然而 ,故 。由 Korselt 判據必有某個單位不通過;取 :
- 模 :,且 ,故 。
- 模 :費馬定理給出 ,故 。又 ,,因此 。
所以 。
反例模式
無平方因子並不足夠:$n=15$
是無平方因子的合數,但 ,因此不是 Carmichael 數。這裏 。
證明中的方法可構造反例: 是模 的原根,解 和 得 。由於 、,有 。
某些底數仍能通過。每個單位滿足 ,所以 ;恰好滿足 的單位通過,即 ,它們是八個單位中的四個。
一個底數與所有底數
對與 互質的單個底數 ,費馬檢驗詢問 是否成立。不成立就由費馬小定理證明 為合數;成立本身不能證明質數性: 通過底數 , 通過底數 。通過某個底數的合數不一定是 Carmichael 數。
Carmichael 條件涉及每個單位,等價於單一整除式 。按定義直接驗證需要檢查 個剩餘類;Korselt 判據把它換成每個質因子一次整除檢查,但前提是已知 的分解,因此它是結構刻畫,不是識別質數的捷徑。
與 有公共因子的底數不在定義範圍內。特別地,,因為 而 。
常見誤解
- 「最小僅僅意味著數值最小。」 結構定理更強:每個通用指數都是 的倍數。
- 「無平方因子的合數都是 Carmichael 數。」 是反例,整除條件不可少。
- 「通過一個費馬底數就意味著是 Carmichael 數或質數。」 是反例。
常見錯誤
(以為 )
這對奇質數冪以及 成立,但對 等不成立。
常見錯誤
(對小的 套用 )
公式要求 ;小指數的正確值是 、。
常見錯誤
(把通用指數用於非單位)
它只適用於單位;非單位的任何正整數次冪都不可能同餘於 。
練習
快速檢查
(計算 ,並與 比較。)
解答
。由最小公倍數公式及兩條質數冪定理,
另一方面,。
快速檢查
(證明對每個 , 都是偶數。 時如何?)
解答 · 答案
設 。因為 ,;而 ,所以 。由結構定理,。當 , 且 為奇數,所以 的假設必要。
快速檢查
(證明 是 Carmichael 數,並計算 。)
解答 · 答案
是無平方因子的合數,且 。因此 均整除 ,Korselt 判據適用。又 ,且 。
快速檢查
(證明每個 Carmichael 數都是奇數,且至少有三個不同的質因子。)
解答
設 是 Carmichael 數,由判據知它無平方因子。
奇性。 若 ,由於 是無平方因子的合數,必有另一個奇質因子 。則偶數 整除奇數 ,矛盾。
至少三個質因子。 無平方因子的合數至少有兩個不同質因子。若 ,其中質數 ,則
由 得 ,但 ,矛盾。故 至少有三個不同質因子,且均為奇數。
快速檢查
(設 是 Carmichael 數,證明對每個整數 ,包括非單位,都有 。)
解答
任取整除 的質數 。若 ,則 模 均為零。若 ,費馬小定理給出 ;由 Korselt 判據 ,故 ,進而 。
因此 的每個質因子都整除 。由於 無平方因子,是這些兩兩互質質數的乘積,故 。
例如 、 時,,儘管 。同餘式 對所有 成立; 只保證對單位成立。