動機
每個質數模數都有原根,但合數模數可能把幾種不同的週期來源結合起來。完整分類既需構造,也需障礙。構造須證生成元的階在每個更高質數冪中,都取得應有的新質因子;障礙則須解釋,為何幾個各自循環的部分,經中國剩餘重建後未必合成一個完整循環。
本篇證明:對每個整數 ,存在原根當且僅當 是二、四、奇質數冪或其兩倍。前篇的質數模原根定理是明確使用的起點;另用已證的階整除判據、Euler 定理、整數質因數分解及中國剩餘定理。不假設任何額外的原根存在定理。
論證區分模質數的剩餘類與其整數代表元。這些代表元到了質數平方會成為不同的類,而差別可能決定階是否增大。構造中加上一個質數的修正,正是來自這個小而重要的區分。
定義
定義 5.2.1
(單位、原根與賦值)
記 為單位類的乘法群,具有 個元素。模 原根是階等於 的單位,等價地是 的生成元。平凡群也循環,所以模二的唯一單位一就是原根。
對質數 及非零整數 ,以 表示使 的最大整數 。凡使用有限賦值的命題均排除 。
模 恰有 個單位,因為被排除的恰是 的倍數。單位的每個返回指數都被其階整除,階又整除單位群大小。這些限制可能的階,卻還未證明最大可能階會出現。
若 互質,中國剩餘映射給群同構 。環映射雙射且保持乘法,一對單位座標有逐座標逆元,其原像亦可逆;反之單位必映到單位。這驗證單位群命題,而不只是比較兩邊數目。
定理 / 命題
定理 5.2.2
(選出能生成全部奇質數冪的提升)
設 奇,正整數 模 為原根。 與 至少一個是模 原根。任何模 原根整數 ,對每個 也都是模 原根。
定理 5.2.3
(所有至少二的模數之完整分類)
對 , 循環當且僅當
其中 為奇質數、。所以恰好這些模數具有原根。
證明思路或證明
先確保質數平方的階
證明
(一次修正確保質數平方)
化簡到模 ,知 模 的階是 的倍數;它又整除 ,故只能是 或 。因此 模 為原根,恰在 時成立。
若此條件成立,取 。若不成立,展開另一提升:
其餘項均含 。係數 模 非零,因 可逆且 。所以第一個冪模 為一時,第二個就不為一。新提升模 仍為 ,相同的階論證使 在模 為原根。這證明最初的存在步驟,無需搜尋平方模數的全部單位。
一步二項展開控制精確賦值
證明
(精確賦值增長給出完整的階)
對奇 ,設有限 ,寫 ,其中 。要證
二項展開首項為 。對 ,第 項因 ,賦值至少 。最後一項賦值為 ,用到了 。因此
首係數仍模 可逆,所以賦值恰為 ,而不只是至少如此。正是這個精確性,排除階增長不足的情況。
化簡 滿射,因每個非零質數層剩餘類都能提升成單位;所以生成元也化簡成生成元。若 為模 原根,則 模 為一、模 卻不為一,因此其與一之差賦值為一。反覆用二項步驟,得
令 為 模 的階。模 化簡給 ,Euler 給 ,所以 ,其中 。賦值式說此冪模 返回一,恰在 時成立,故 ,階正是 。同一整數 適用於每個 。
證明透視
返回冪不等於精確階證書
三個事實確定 模 的階 ,每個排除一種不同的損失。由於 模 約化為生成元,其階是 的倍數。歐拉(Euler)定理給出 ,所以 ,其中 。關鍵一步是精確賦值 :若只有不等式 ,只能說明某個冪回到 ;等式則說明對每個 都有 。
為奇數只在一處用到,即二項展開的最後一項:只有當 時, 的賦值才至少為 。對 與 ,這一步失效,因為 而不是 。起始情形 正是第一步所確保的平方層原根性。
構造允許的偶模數
證明
(偶模數的存在性)
模 、模 的單位群直接可見是循環群,生成元分別為 、。奇 時,前面定理由質數層生成元構造每個 的原根。
由 平凡,CRT 給 。所以模 的生成元,有唯一奇數提升到模 ,且階不變。給定代表元 ,奇時取 ,偶時取 。奇偶檢查不可省,偶代表元根本不是加倍模數的單位。至此每個列出類型均已證存在。
過多的一之平方根阻止單一循環
證明
(四個一的平方根與必要性)
在 階有限循環群,把元素寫成生成元冪,則 等價於 ,只有 個解。因此若單位群有四個不同的一之平方根,就不可能循環。
當 ,模 的四類
互異且均為單位,平方皆一。展開 得 ,後兩項模 消失。互異使用 ;模 時候選類兩兩重合。所以 時 沒有原根。
每個奇質數冪單位群都有互異的一、負一兩根。若模數有兩個不同奇質因子,便在這兩個 CRT 座標獨立選正負號,其餘座標取一,得到四個互異、平方為一的重建單位。模數同時有四因子及奇質因子時,也可如此,因模四座標同樣有不同的正負號。若二冪座標更高,它本身已有四根,可配上其餘座標的一。這些單位群都不循環。
為確認沒有漏掉模數,寫 ,各 為不同奇質數,。若 ,由 知 ,只餘 ;若 ,只餘 ;若 ,獨立奇數座標的符號已排除循環。留下的恰是定理類型。這完成必要方向,而非只給幾個失敗例子。
證明透視
一個不變量排除所有被排除的模數
必要性證明只用一個不變量: 的解的個數。在循環群中它至多是二,因為 有 個解;這是循環性唯一出場之處。其餘部分都在製造四個解。對 的 ,四個解可以明確寫出,而假設 正是令 與 不同的條件。其他情況由 CRT 推動:兩個各自含有相異符號 的座標給出獨立的選擇。最後的分解計數說明,這兩種機制覆蓋了列表以外的每個模數。
例題詳解
例題 5.2.4
(質數層生成元可能有錯誤提升)
整數 模 的類為 ,所以是原根。但 ,其模 的階只有 ,而非 。改成 ,有 ,賦值為 。所以 對每個 都是原根。模 時其階為 ;其六次冪為 ,所以較小的候選指數 並不足夠。修正把同一質數層代表元,改成平方層真正不同的類。
例題 5.2.5
(奇數提升給模五十生成元)
由於 , 是模 的原根,且 。因此 生成模 的單位,但它是偶數,不是模 的單位。所需的奇提升為 ,階仍為 。直接驗證 、,排除 的極大真因數 與 ,給出獨立的精確階證書。模 共有 個原根,由此生成元的互質指數冪得到。
例題 5.2.6
(循環座標未必給循環直積)
的局部單位群都是循環群,階分別為 與 。但模 時 的平方都是 ,故全局群不循環。兩座標的生成候選同時返回,由最小公倍數而非乘積控制。特別地, 模 的階為 ,而 。很長的冪循環,未必就是完整循環。
概念視角結構
CRT 同步不同的返回時間
直積元素的分量階為 時,其階為 ,因恰在兩個分量階都整除指數時返回。對階為 的循環因子,每個分量階都整除因子階,故直積元素階都整除 ,而一對生成元達到此界。因此直積循環當且僅當 。兩個奇質數冪單位群的階均偶,循環共享因子二,不能合成與直積大小同長的循環。CRT 保持乘法,並未說獨立循環的長度互質。
常見錯誤
反例模式
原根的提升不一定是平方模的原根
一個看似合理的說法是:模奇質數 為原根的整數,模 也仍是原根。模 時整數 是原根, 亦然。但 ,故 ,而 。因此 , 的階為 ,不是 。相反,,所以 本身是模 的原根。正確的說法是提升定理: 與 至少有一個可行;而一旦模 的階達到最大,所有更高的冪都隨之成立,無須另選生成元。
常見錯誤
(以為局部循環便給出循環直積)
每個 CRT 座標的單位群都循環並不足夠,只要兩個座標的階有公因數。模 時, 與 分別是階 與 的循環群,但每個單位都滿足 ,所以沒有單位的階為 。
常見錯誤
(把域上的根數界搬到合數模)
「二次多項式至多有兩個根」只在域上成立。模 時, 的四個根 確實存在;它們矛盾的是循環性,而不是多項式的界。檢查階或計算生成元時,也要分清取值模數 與指數模數 。
總結
加上一個質數的修正,確保奇質數平方的原根;精確賦值增長再證每個高冪都有最大階。CRT 把生成元轉到兩倍模數,四個獨立的一之平方根則排除其餘全部類型,完成 分類的兩個方向。
練習
快速檢查
(固定奇質數 的正原根 。證模 的 個提升 中,恰一個不是原根;解釋只查 為何總能成功。)
解答 · 答案
由 Fermat 寫 。二項式給 。 的係數模 可逆,恰一 使括號零;恰該提升階為 ,其餘階為 。若 失敗, 成功;若已成功,毋須修正。保證的是兩者至少一個,不是兩者總都是原根。
快速檢查
(從 模 開始構造模 的原根,並給出直接的階證書。)
解答 · 答案
由於 的賦值為 , 是模 的原根;它到模 的奇提升為 。計得 、。階整除 ,卻不整除 或 ,故恰為 。這兩者是 的極大真因數 與 ,因而排除全部較小因數。
快速檢查
( 中哪些有原根?對每個允許者給一生成元,並以構造或前例說明。)
解答 · 答案
恰 符合,生成元依次為 。 生成模 的單位且本身是奇數,故適用於模 ; 因 而生成模 的單位,且本身是奇數,故適用於模 ;由賦值檢驗, 適用於 與 的各次冪; 已在模 證明。其餘模數具有禁止的二冪因子,或至少兩個不同奇質因子,正是分類排除的情形。
快速檢查
(解釋賦值步驟為何不能直接套到 。用 計算,並聯繫原根由 提升到 的失敗。)
解答 · 答案
,但 ,不是 。二項證明在 時,最後項賦值未必至少 ,可與首項互相影響。 生成模 的單位,模 時階卻只有 ,而非所需的 。這是真正的群結構障礙,四個一之平方根也可證明,不只是奇質數證明存在缺口。