動機
問指定剩餘是否在平方映射的像內。原根把它化為指數同餘,但計算離散對數可能是多餘工作。二次互反律改為比較不同質數模數;配合幾條初等補充規則,能把許多剩餘問題縮成更小者。
論證有幾個階段:先以兩種符號辨認非零剩餘,再從帶符號代表元的有限置換找出符號,最後用兩種方式計算同一格點矩形。這會解釋互反的負號,而不是只要求記住兩質數模四餘三時的例外。
主要論證的質數均為奇數。前篇已證域的根數上界、質數模數的 Fermat 定理及基本同餘運算。不能把質數換成奇整數,便暗中宣稱已得到所有合數模數的結果。
定義
定義 6.1.1
(二次剩餘與 Legendre 符號)
對奇質數 ,非零剩餘 若可寫為 、,稱為二次剩餘;否則稱為二次非剩餘。定義
Legendre 符號只依賴分子的模 類。它不是分數,沒有已證符號恆等式時,類似分數約消的操作沒有意義。
非零平方恰有 類。非零類的平方映射恰把 成對識別: 給域中的 ,故 或 ;奇特徵使兩者互異。這個初等計數是下面 Euler 準則的起點。
概念視角代數
符號即離散對數的奇偶性
若 是模 的原根, 且 ,則
指數是模偶數 來讀的,所以 的奇偶性有明確定義。偶指數顯然給出平方;反過來, 給出 ,指數為偶。從這個角度看,符號就是由循環單位群到 的唯一滿同態,而對分子的乘法性立即可見。
定理 / 命題
定理 6.1.2
(Euler 判別準則與 Gauss 引理)
若 ,則
令 。對 ,以 表示 的最小正模 代表元,以 計算其中 的數目。則
定理 6.1.3
(二次互反律及補充律)
對不同奇質數 ,
對每個奇質數 ,
兩個互反符號恰在兩質數都模四餘三時相反,其他情況相同。
證明思路
證明
(以平方數計數證明 Euler 準則)
令 。每個非零平方 由 Fermat 滿足 模 。這些類恰有 個,而域上的 至多有 根,所以非平方不可能滿足此式。任意單位又由 Fermat 得 ,分解平方差知 只能為一或負一。非平方只可能為負一,證明 Euler 準則。
由此符號對分子具乘法性。對單位 ,Euler 準則使 等於對應兩符號的乘積。模奇質數時一與負一不同,所以整數符號相同。若某分子被 整除,乘法式兩邊均零,故規則適用於全部整數分子,也證明後續可分解分子來計算。
帶符號置換證明 Gauss 引理
證明
( 的帶符號置換)
若 ,取 ;若 ,取 。這些代表元在 內,絕對值互異:若相同,則 ,故 。索引在一至 ,正號迫使相等,負號由 排除。因此絕對值恰排列 。
把帶符號代表元相乘,一方面乘積同餘於 ,另一方面恰等於 。 的全部因子均不被 整除,所以可合法消去,再用 Euler 準則即得符號公式。證明需要的是絕對值的置換,而非聲稱正剩餘本身就是 。
補充律
證明
(對 與 計算越界次數)
對 ,最小正代表元為 ,全大於 。Gauss 計數 給第一律。對 ,代表元就是未回捲的整數 ,其中恰有
個超過 。當 模八依次餘 ,此數奇偶依次為 ;整數 的奇偶亦相同。因此 Gauss 引理證第二律,涵蓋每個奇質數類。二由補充論證處理,不是套用要求兩奇質數的互反公式。
把符號化為下整數和
證明
(把 Gauss 計數寫成下整數和)
需要一個奇偶恆等式。令正奇整數 與 互質,寫
並令 為 Gauss 引理中的絕對代表元,其和為 。把負的 換回正剩餘 ,得到
模二即 。另一方面, 均奇,把除法等式相加得 。比較得 ,故
奇偶論證使用了 的奇性。忽略假設而用於任意偶分子,便會失去剛剛追蹤的符號資訊。
下面的互動圖對任意奇質數 及分子 ,數出 大於 的剩餘個數,把 Gauss 符號與 Euler 判別準則及逐一列出的平方數比較,並顯示下整數公式在 為偶數時何處失效。
反例模式
下整數和公式需要奇分子
一個誘人的說法是:對每個與 互質的分子都有 。取 、,則 ,而 ,預測符號為 。但模 的非零平方只有 與 ,所以 。Gauss 計數本身是正確的:剩餘 中恰有一個大於 ,故 。奇偶步驟 用到 為奇數,在此失效。對 應改用補充計數 。
一個矩形完成互反律
證明
(計算矩形中的格點)
令 、。考慮 、 的 個整數點 。沒有點在直線 上,否則由兩不同質數的性質得 ,與範圍矛盾。
固定 時,滿足 的點數為 。由 ,它不超過 ;又無整數邊界相等。固定 時同理, 的點數為 。兩類互不相交且分割全部矩形,故
先對分子 ,再對分子 用下整數符號式,相乘得 ,正是互反律。每個格點只數一次,而沒有邊界點正是使用不同質數假設之處。直線兩側的點數不必相同。互反律使用的是兩計數之和的奇偶,而非兩計數相等;這也解釋為何面積為奇數的矩形會產生相反符號。
證明透視
幾何計數為何決定算術符號
這條推理鏈有三座橋,各用一個不同的假設。Gauss 引理把符號化為負代表元個數 的奇偶;它只需要 為奇數,使 為整數且 。下整數和恆等式則需要奇分子,因為它在模 下比較 與 。互反律把它用了兩次,分子分別是 與 ,所以兩個質數都必須是奇數。
關鍵一步是矩形。每個下整數和計算直線 一側的格點;兩質數相異保證沒有格點落在直線上,所以兩個計數之和恰為 。兩側的格點數不必相等:、 時兩側各有一點;、 時兩個計數分別為 與 。只有總數的奇偶才重要,而特殊符號 正是矩形面積的奇偶。
例題詳解
例題 6.1.4
(不找平方根也能計算符號)
求 。兩質數均模四餘一,故互反給 。乘法性化成 。由三十七模四餘一,再互反得 。因此三十七是模一百零一的非零平方。這決定存在性,卻未構造平方根;兩者是不同任務。
例題 6.1.5
(先判剩餘,再驗證實際根)
對 ,互反符號為正,得到 。十三是根,因為 ;其負為二十八。兩者互異且為全部根,因域上二次多項式至多兩根。符號證存在,代入找到見證,根數界證完整。
例題 6.1.6
(合數符號不能取代質數定理)
對正奇整數 ,定義 Jacobi 符號 , 的空乘積為一。於是 。但二不是模十五平方,因任意候選根模三後都須平方為二,不可能。又 ,所以把 Euler 準則的 換成十五也失敗。Jacobi 符號是局部符號乘積,並非完整的合數平方檢驗。
可靠的計算流程
先檢查分子是否模質數為零,若是則符號零。否則選方便代表元,用已證恆等式分出負號、二因子或重複平方因子。對奇質因子互反,先記錄負號再化簡新分子。連續較小模數組織計算,但沒有聲稱大分子的因數分解免費。
最後問符號究竟證明甚麼。正 Legendre 符號給非零目標兩根,不給其公式;負符號排除根。正 Jacobi 乘積卻可能留下不相容的局部符號。把判定、構造與完整性分開,可防止高效符號運算承擔未證明的結論。
把非零平方根提升到奇質數冪
可控地離開域,仍有有用推廣。固定奇質數 ,設 ,且 時 。此類到模 的每個提升均為 , 取模 。寫 ,展開平方得提升為根當且僅當
餘下 因 而模 消失。由 奇且 模 非零, 可逆,故 唯一。每個非零根因而唯一提升至所有更高冪。高模數根必化簡成低模數根,所以這同時給存在與完整性,而非只列候選。
例如五模四十一的根十三有 。下一式為 ,解為 ,故 是模 的根:。其負給另一提升根。這是在已知質數層根後構造提升,互反律本身沒有找到最初的根。
最後,正奇合數可分為不同質數冪因子,並假設目標與模數互質。按 Legendre 符號,每個質因子在所有冪次上不是無根,就是兩根;中國剩餘定理獨立組合各選擇。因此任一局部符號負便無根,否則恰有 根, 為不同質因子數。這不涵蓋非單位目標或二的冪,因提升式的可逆性可能失效,也精確解釋正 Jacobi 乘積為何弱於逐項檢查局部符號。
常見錯誤
常見錯誤
(兩質數都模 餘 時漏掉負號)
對 ,兩個質數都 ,所以互反律給出 。漏掉負號便得 ,這是錯的:模 的非零平方是 ,其中沒有 。
常見錯誤
(對合數或偶數分子使用互反律)
互反律聯繫的是兩個相異的奇質數。像 這樣的符號不能倒轉為「」,後者不是 Legendre 符號。應先分解:,其中 用第二補充律,只有 用互反律。驗算: 且 ,給出 。
Euler 準則是同餘式,右邊為整數零、一或負一;Gauss 引理則是符號等式。兩者連接使用模奇質數時一與負一仍不同。合數環可能有額外的多項式根及非單位因子,因此兩證明的域假設不可忽略。
總結
Euler 準則以符號編碼平方性。Gauss 引理由帶符號剩餘置換取得符號,補充律處理負一及二,格點矩形給互反負號。完整證明可判定許多質數平方問題,同時清楚限制找根與合數結論的範圍。
練習
快速檢查
(計算 、,指出使用哪條補充律。)
解答 · 答案
,故 ;,故 。兩者均用已證補充律,不是與偶質數互反。
快速檢查
(計算 、;後者為正時,找出並驗證 兩根。)
解答 · 答案
、 均 ,所以 。另一對給 。根為 、,其平方 、 均 。兩者互為負,域根數界排除其他根。
快速檢查
(直接以 Gauss 引理算 ,列帶符號代表元及負數個數。)
解答 · 答案
模 的正剩餘為 ,帶符號代表元為 。恰有一個負,故符號為 ;絕對值 明確展示所需置換。
快速檢查
(證明若 ,且 是正奇數 模下的平方,則 Jacobi 符號為一;解釋反向為何失敗。)
解答 · 答案
對 每個質因子化簡平方,由互質性得到非零平方,故全部 Legendre 因子均為 ,其冪乘積亦為 。 反駁逆命題:兩個負局部符號相乘為正,但兩局部平方式都無解。