動機
歐拉(Euler)定理給出了每個單位的循環週期的上界,但並不保證存在一個包含所有單位的循環。原根恰好提供這一點:每個單位都成為某個選定剩餘類的冪。於是乘法變為指數的加法,看似非線性的冪方程化為線性同餘。存在性證明依賴於質數模的一個特徵,而合數模可能不具備該特徵:域上多項式的根的個數上界。
定義
定義 5.1.1
(原根與離散對數)
模 的原根是滿足 的單位 。此時它的冪 恰好是全部單位,且沒有重複。相對於 ,單位 的離散對數是模 的唯一指數類 ,滿足 。
離散對數是一個指數的剩餘類;選取其中一個整數代表元則是進一步的約定。其定義並不斷言它容易計算。這裏的小型表格只是用來說明代數結構,而不是暗示存在一般的高效算法。
定理/命題
定理 5.1.2
(質數模的原根)
對每個質數 ,模 的單位群存在原根,且恰有 個原根。質數 也包括在內:它唯一的單位 的階為 ,而 。
定理 5.1.3
(在循環單位群中解冪方程)
設 是模 的原根,令 ,並把單位寫成 。對正整數 ,方程 的單位解透過 與 的解一一對應。因此,除非 ,否則沒有單位解;若此條件成立,則恰有 個解。
證明思路
證明
(以互質的階合併各質數冪部分)
首先,域上 次非零多項式至多有 個根。若 是一個根,多項式除法給出因式 ;由於域中沒有零因子,對次數作歸納即可約束其餘的根。這適用於模質數的剩餘類。
設 為奇質數,並寫 。對每個滿足 的質數 ,多項式 的根少於 個,因此可選取非零剩餘類 使 。設其階為 。由歐拉定理得 。因為 ,所以 中 的指數恰為 。因此
由冪的階公式,其階為 。
階互質(分別為 )的可交換元素,其乘積的階為 。事實上,若 ,則 同時屬於兩個循環子群。它的階同時整除 ,故為 。於是 且 ,從而 ;而指數 確實成立。反覆運用這一事實,可知 的階為 。這就證明了存在性。
每個單位都是 的形式。其階為 ,所以它是原根當且僅當 。這樣的指數類共有 個。
證明
(指數座標把冪方程化為線性同餘)
寫 、。由階的判別準則, 等價於 ,再由線性同餘定理得到解的個數。特殊的指數模 只有一個類,結論直接成立。
證明透視
域與互質的階分別在哪裏用到
域只用到一次:根的上界保證次數為 的 不可能在全部 個非零剩餘類上都為零。由此得到元素 ,其階 整除 但不整除 ,所以 含有完整的冪 。被選元素不必是生成元;冪 去掉不需要的因子,其階恰為 。
關鍵一步是互質階引理,它需要兩個假設。可交換性使 能分拆為冪的乘積,而互質的階使兩個循環子群只在 處相交。在單位群中,兩者都由構造保證,而這些質數冪階相乘正好是 。模 時根的上界失效,因為 有四個根,而確實沒有任何單位的階為 。
例題詳解
例題 5.1.4
(模 7 的完整冪表)
模 下, 依次為 。由於六個單位全部出現, 是原根。原根對應的指數與 互質,即 ,所以原根是 和 。特別地,階最大並不意味著數值最大的剩餘類。
例題 5.1.5
(從三次方程到線性同餘)
解 。由表知 ,令 ,解 。解為 ,得 。它們的立方的餘數都是 。非單位不可能是方程的解,因為它的立方不是單位。
例題 5.1.6
(質數模與合數模的表現不同)
模 時,單位 的平方都是 ,所以沒有單位的階為 ;不存在原根。此外 模 有四個根,超過其次數。這並不與多項式根的個數上界矛盾,因為該上界的域假設不成立。相反, 模 的階是 :由模 的約化知其階被 整除,又整除 ,故為 或 ;而 排除了 。
生成元對歐拉定理增添了甚麼
歐拉定理告訴我們,每個單位在一個共同的指數處回到一。它並沒有說單個單位的冪能到達其他單位。原根增添了一個完整的座標系:每個單位被賦予一個指數類,乘法對應於座標的加法。這是比週期性更強的結構性論斷,需要單獨證明。
這一區別在模八時清晰可見。每個單位都有短循環,但沒有一個循環長到包含全部四個單位。分開的兩元素循環不能僅靠選取更方便的代表元而連接起來。更換代表元不會改變剩餘類及其階。因此,循環性的失敗是乘法結構的性質,而不是所選記號的問題。
為甚麼多項式論證需要域
根的個數的證明反覆提取一個線性因子,並論證其他每個根必為剩餘因式的根。這一推導用到了沒有零因子。在域上,若乘積為零且一個因子非零,則另一個因子必為零。在合數模的剩餘類環中,兩個非零因子的乘積可以為零。因此,在域上安全的次數上界可能失效。
在存在性證明中,所選多項式的次數嚴格小於域的非零元素個數。因此它不可能在所有非零元素處都為零。所選元素並不被聲稱立即就是生成元,它只貢獻所需階中一個完整的質數冪部分。這是核心的策略:分別解決若干較小的階的要求,再利用互質性把它們合併。
反例模式
乘積的階不一定是階的乘積
一個誘人的捷徑是:把階為 與 的任意兩個單位相乘,便期望得到階 。模 時,單位 與 的階都是 ,因為 且 。它們的乘積是 ,階為 ,而不是 。這裏 與 生成同一個子群,所以相交論證失效。若階互質,結論便成立: 的階為 , 的階為 ,而 的階為 ,所以 是模 的原根,與冪表一致。
不必列出每個循環即可計數生成元
一旦知道一個生成元,階公式就一次過刻劃了其他所有生成元。與群的大小互質的指數保持完整的循環,而有公因數的指數只訪問較短的子循環。這把生成元的計數化為對互質指數類的計數。答案取決於群的大小,而與具體選取了哪個生成元無關。
這一計數並不循環論證。生成元的存在性先由多項式構造證明。之後我們才用它的冪來枚舉所有單位,並計數那些具有最大階的單位。若一開始就把每個單位寫成某個未指定生成元的冪,就等於假定了主定理。把存在性與枚舉兩個階段分開,是代數證明中一個有用的普遍習慣。
一個小質數可以使這一區別更清楚。知道某個候選元在完整指數處的冪等於一,僅僅是歐拉條件。要證明它是生成元,必須排除該指數的每個真因數作為回歸時間。僅檢驗候選元不是一,只排除了階為一的情形,而其他所有真階都未排除。前面的因數檢驗方法提供了一個簡短而完整的證明憑據。
快速檢查
(只計算兩個冪,證明 是模 的原根。)
須排除的 的真因數,都整除 或 。
解答 · 答案
的階整除 。若它是真因數,便會整除 或 。但 ,,兩者都不是 。因此階為 , 是原根。
變換座標後解方程
從指數類到單位的映射是雙射。因此,在指數座標中解方程既不會產生多餘的單位解,也不會漏掉有效解。指數的線性同餘可能有多個解;由於座標映射是單射,這些解給出互不相同的單位。這就是線性同餘解的個數可以直接轉移到原冪方程的原因。
可解性條件用到了目標元的對數,但不依賴於選來代表該對數的具體整數。任意兩個代表元相差群的大小,而群的大小被條件中出現的最大公因數整除。因此更換代表元不改變該最大公因數是否整除目標指數。這是一個小小的良定檢驗,凡涉及指數類的陳述都應伴隨這一檢驗。
更換原根也不改變解的個數。任何新的原根都是舊原根的一個互質次冪,所以更換座標相當於把指數乘以一個模群大小的單位。線性同餘被雙射地映為相應的新同餘。數值上的對數改變了,但原方程及其解集不變。
概念視角結構
冪方程化為像與纖維的問題
在指數座標中,把單位取固定次冪就是把其指數乘以一個固定整數。它與循環長度的最大公因數同時度量了核的大小(即給定次冪為一的單位個數),以及任何可達目標的原像個數。像之外的目標沒有原像。這與係數為非單位的線性同餘中已見的結構相同。
作為第一個推論的二次剩餘
對奇質數,取一個原根並考慮單位的平方。指數循環的長度為偶數。因此平方數的指數為偶數,而每個偶指數都可透過把某個指數加倍得到。恰有一半的非零剩餘類是平方數。每個這樣的剩餘類在單位中有兩個平方根,對應於加倍指數同餘的兩個解。它們互為相反數,因為在奇特徵下非零的根不可能等於其相反數。
這一結論是引入二次剩餘的有用開端,但它並未證明二次互反律,也沒有給出一般的高效平方根算法。生成元表可以解決小的例子,而大的情形則需要額外的計算思想。應當區分可能解的代數分類與求出其座標的難度。離散對數由唯一性來定義;其計算成本是另一個問題。
當前論證的邊界
質數冪的例子表明某些合數模確實有原根。模八的例子表明有些則沒有。兩者合起來防止了兩種錯誤的推廣,但並未建立完整的分類。完整的處理需要考察從奇質數提升到其冪,以及與因數二的相互作用,然後證明相應的必要性命題。這些主題不在本頁已完成的證明範圍之內。
這一邊界是數學上的,而不僅僅是行政上的。多項式根的論證在域上有效,所以不能不加修改地在每個合數模剩餘類環上重複。任何推廣都必須用新的推理來取代缺失的假設。認識到一個證明在何處失效,往往是通向下一個正確定理的第一步。
常見錯誤
常見錯誤
(只檢查完整指數而不檢查每個真因數)
滿足 及 的單位 不一定是原根:歐拉定理對每個單位都給出第二個條件。模 時,單位 滿足 ,但早已有 ,所以其階為 。原根要求對每個質數 都有 。對合數模,原根根本不一定存在,而上面的證明只涵蓋質數模。
常見錯誤
(把指數模 約化而不是模 )
指數座標以 為模,而數值以 為模。對 及 ,正確的同餘式是 ,有三個解 。若改為模 ,得到 ,只有 ,於是遺漏了解 與 。解的個數亦只針對單位目標與單位解;零目標需要另行做整除性分析。
總結
域上根的上界產生具有每個所需質數冪階的元素。它們的互質階之積生成模質數的全部非零剩餘類。一旦固定了生成元,冪方程就化為關於指數類的線性同餘。
練習
快速檢查
(利用模 的原根 ,列出模 的所有原根。使用階公式,而不要重新計算每個冪的循環。)
解答 · 答案
與 互質的指數是 。它們對應的 的冪模 分別為 。這恰好是 個原根,因為每個的階都是 ,且每個單位都是 的冪。
快速檢查
(解 ,並證明 無解。使用 的冪表。)
解答 · 答案
由於 ,第一個方程為 ,解為模 的 。因此 模 。對目標 ,方程為 ,由於 ,無解。剩餘類 不是任一單位目標方程的解,所以這些結論窮盡了所有剩餘類。