動機
由於剩餘類只有有限多個,模整數的重複乘冪最終必然重複。對於單位,消去律把這種重複拉回到 :它的各次冪構成一個從單位元出發的真正循環。這解釋了為何大指數可以化簡,也解釋了為何必須先檢驗互質,這種化簡才算合理。
定義
定義 3.1.1
(歐拉(Euler)函數與乘法階)
對 ,設 為模 的單位所組成的集合,並令 。若 ,則階 是滿足 的最小正整數 。
為說明階的存在性:在 之中必有兩個冪相等。以較小冪的逆元相乘,便得到一個等於 的正次冪。由良序原理,符合條件的最小指數存在。此假設排除了例如模 的 這類數,它的正次冪永遠不等於 。
定理/命題
定理 3.1.2
(歐拉定理與費馬(Fermat)小定理)
若 且 ,則 。特別地,對質數 且 ,有 。對每個整數 (包括 的倍數),都有 。
定理 3.1.3
(階刻劃所有的返回時刻)
若 ,則對每個非負整數 , 當且僅當 。因此 。更一般地,對正整數 ,
證明思路
證明
(乘以單位是單位集合的置換)
乘以單位 會置換 :它把單位映為單位,其逆映射是乘以 。取代表元 ,其中 。把所有像相乘,得到
單位之積有逆元,所以消去後即得歐拉定理。對於質數 ,每個非零剩餘都是單位,因此 。當 時,乘以 即可證明對所有整數成立的版本;當 時, 與 模 都為零。
證明
(對指數作帶餘除法)
關於階的判別準則,寫 ,其中 。於是 ;若它等於 ,由最小性可得 。反方向則對 取冪即可。這個論證亦包括 的情況。最後, 恰好當 時成立。令 ,寫 ,,且 ,則該條件等價於 。其最小正解為 ,公式得證。
證明透視
帶餘除法給出逆命題
知道階本身是返回指數,只證明了它的倍數都會返回。要證明返回指數只有這些,可將任何給定的指數除以階。餘數也會是返回指數。由於它小於最小的正返回指數,只能為零。正是這個逆命題,令往後所有的因數檢驗與生成元計數得以成立。
這些都是關於單位的精確陳述,並不是說每個階都等於 。歐拉定理給出的是對所有單位都有效的公共指數;個別循環可以更短。
例題詳解
例題 3.1.4
(大指數與小循環)
模 ,有 及 。階為 ,因為 且 。因此,由於 ,得 。這個計算用的是真實的返回指數,而不是對冪的某種近似。
例題 3.1.5
(透過排除真因數來確定階)
模 ,由費馬定理得 。 的任何真因數都整除 或 。但 ,,兩者都不是 。因此 。再由階的公式,。
例題 3.1.6
(通過費馬檢驗並不能證明是質數)
合數 滿足 ,因為 。於是 。它雖是合數,卻通過了以 為底的費馬條件。在正確運用假設的前提下,檢驗失敗可以證明是合數,但單憑檢驗通過並不構成質數的證明。
為何有限重複只對單位才成為循環
由重複乘法產生的有限個剩餘狀態序列,最終必然重訪某個狀態。若不具備可逆性,重複的片段不必包含初始值 。例如,模 時 的各次正整數冪會到達零並停留在零。這個過程有一段短的重複尾段,但從不正向返回到 。把該尾段的長度稱為乘法階,既違背定義,也會令證明中每一次使用消去律都失去根據。
對於單位,乘法是全體剩餘上的一個置換,並且有逆置換。若兩個冪相等,便可以按較小的指數向後退。於是返回從 開始,不可能存在過渡部分。在第一次返回之前,循環中的每個位置都互不相同。這給出階的有限狀態詮釋,而且完全保持在代數範圍之內:關鍵要素是轉移的可逆性。
概念視角結構
階作為可逆軌道的長度
考察 在乘以某個固定單位下的軌道。該軌道會回到 ,並且恰由第一次返回之前的各次冪構成。把指數按階化簡,就是在這條軌道上選取同一個位置。歐拉定理的指數可能繞軌道若干圈,它不必等於軌道的長度。
歐拉乘法論證用到了甚麼、沒有用到甚麼
歐拉定理的證明常被壓縮為「把簡化剩餘相乘」。被相乘的集合必須說清楚:它包含每個單位類的一個代表元,而不是每個非零剩餘。對於合數模,存在非零的非單位,把它們包括進來會令乘積不可逆。這樣一來,消去這一步便沒有根據了。證明之所以成立,是因為所選的乘積在每一步都是單位。
無須斷言乘以單位後這些代表元的數值或次序保持不變。保持不變的是它們的類所構成的集合。約化之後代表元可以改變,但每個單位類恰好出現一次,因為乘以單位既是單射又是滿射。因此,完整代表元列表的乘積彼此同餘。這是關於置換的陳述,而不是關於整數的某種方便排序。
也可以把這個證明看作有限群論證的特例。用那種語言來說,單位在乘法下構成群,歐拉指數就是該群的階數。直接的置換證明的好處是每一步消去都清晰可見,而且不需要事先具備任何群論定理。日後的代數可以更一般地組織同樣的推理,但這個初等證明本身已經完整。
在得到指數上界之後高效確定精確的階
假設已經證明某個指數能使單位回到 。精確的階必定整除該指數。因此無須檢驗它以下的每一個正整數。對該指數作因數分解,對每個質因數,檢驗去掉一個該質因數之後是否仍是返回指數。如果是,就用較小的指數取代當前上界並繼續;如果不是,則該質數冪的貢獻不能從當前上界中去掉。
這個化簡的正確性來自每個返回指數都被階整除。當某個質因數被成功去掉時,階仍整除新的上界。若沒有任何質因數可以去掉,則不可能還剩下真因數:任何真因數都至少欠缺上界的一個質因數,因而整除某個已被檢驗過的較小指數。這與已失敗的檢驗相矛盾。此程序明確了兩項責任:先證明一個返回上界,再排除所有更小的因數可能。
對於有許多小因數的指數,這可以顯著減少檢驗次數。但它並不使整數分解變得毫無代價,也不是對任意大模數的一般複雜度斷言。數學上的結論只是:因數結構可以組織對階的有限搜尋。只要對固定模數始終一致地作約化,便可以用反覆平方來完成冪的檢驗,而無須展開龐大的整數。
冪的階刻劃子循環
在循環中每隔兩個、三個或更多個點取一個,可能只訪問較少的位置。冪的階公式恰好量度了訪問多少個位置。如果步長與循環長度有公因數,則遊走被限制在相對於該因數的某一個同餘類的位置之中。如果兩者互質,則每個位置最終都會被訪問。這就是為何一個生成元的冪本身是生成元,當且僅當其指數與原來的階互質。
舉一個小模型:把十個位置排成一圈。每次移動四個位置,則在返回之前訪問五個位置;每次移動三個位置,則訪問全部十個位置。兩種情況的算術解釋相同:第一個正的移動次數必須令步長與移動次數之積被十整除。這裏不需要任何幾何假設;圓只是把定理中證明的整除條件展示出來。
解讀質數檢驗而不顛倒蘊含
費馬定理的邏輯形式是:如果模數是質數且底不被它整除,則某個指定的冪回到 。其逆否命題是:在已核對底的條件的前提下,這種返回的失敗可以排除是質數。其逆命題會說返回就證明是質數;前面的合數例題駁斥了這一點。這種區分是邏輯問題,與數值精度無關。
對多個底通過檢驗可以提供更多的證據,但這裏所陳述的初等定理並不會把任何未經說明的若干次通過變成證明。嚴格的證明需要另一條帶有自身假設的定理。尤其是,找到某一個底的短冪循環,只是描述了該底的階;它並不決定所有剩餘的結構,也不決定模數是否為質數。把這些結論區分開來,可以避免要求一次有效的計算去證明它實際上並未確立的內容。
在起點處檢驗所聲稱的週期
對單位所提出的指數週期,可以在 處檢驗:它是週期,恰好當底的這個次冪等於 。如果成立,乘以任意次冪便可看出,把任何指數平移所提出的週期,值保持不變。反過來,對所有非負指數都有效的週期,尤其是必須在指數零處保持該值,因此必須回到 。這個等價關係把週期序列的語言直接與階的定義連繫起來。對於非單位,最終週期可能只在一段初始部分之後才成立,模 時 的冪便說明了這一點。因此,檢查該序列後段的值,並不能證明可以化簡較前的指數。務必說明週期性是從零開始,還是僅在某段過渡部分之後才開始;只有前一種說法才支持用所聲稱的週期對非負指數作無限制的化簡。
常見錯誤
常見錯誤
(底不是單位時化簡指數)
按 化簡指數需要底是單位。模 時,把指數 化簡為 ,會錯誤地把 與 視為相同。指數同餘並不自動意味著任意底的冪同餘。
常見錯誤
(把費馬定理倒過來,或假定階最大)
費馬定理的逆命題也不成立, 即是例子。即使模數為質數,階也不必取到最大:模 ,類 的階為 ,儘管 。要確立一個階,既要給出一個返回指數,也要說明為何沒有更小的因數可行。
反例模式
費馬定理對所有整數的形式需要質數模
命題:既然 為質數時 對每個整數成立,那麼對每個 及每個整數 ,都有 。取 、。則 ,而 ,但 。質數的情形之所以成立,是因為模 唯一的非單位是 ,任何次冪都保持它不變;模 時非單位 不是零,卻有 。修正後的敍述是把歐拉定理乘以 ,因此要求 ;沒有這個假設時,本節只對質數模保證此同餘式對每個整數成立。
總結
歐拉定理來自對單位的置換。帶餘除法把最小返回指數變成對每個返回都適用的整除判別準則。冪的階則由整數條件 的化簡得出。
練習
快速檢查
(求 模 的階,並計算其立方的階。)
先得到一個指數上界,再檢查它的因數。
解答 · 答案
,,且 。因數 都不回到 ,所以階為 。 的階為 ,與 一致。
快速檢查
(證明:模 的單位的階恰為 ,當且僅當它的平方為 而它本身不是 。列出模 的所有這樣的單位。)
對於合數模,階為 的元素不必是剩餘 。
解答 · 答案
階為 ,恰好意味著指數 回到 而指數 不回到。反之,如果這兩個條件成立,則最小正返回指數整除 且不是 ,所以是 。模 的單位為 ,它們的平方都是 。因此 恰好是階為 的單位。
快速檢查
(計算 模 的值,並解釋為何可以化簡指數。)
使用 之前,先檢查是否互質。
解答 · 答案
由於 ,歐拉定理給出 ,所以指數可以模 化簡。因為 ,得 。事實上 、,所以 ,不能再作更小的化簡。