為何只處理單位不足夠
對奇質數 ,現有二次剩餘筆記處理與 互質的目標。若目標可被 整除,根也可能可被 整除,因此導數 不再模 可逆;直接套用單位根的提升步驟會忽略情況的變化。
我們每次只處理一個奇質數冪。以下 為奇質數、;除另有註明外,同餘模數均為 。
定義 6.2.1
( 進賦值)
對非零整數 , 是使 的最大整數 。於是 ,其中 ,並且 。若 ,則 。我們不給 指定有限賦值。
模質數冪非零的目標
定理 6.2.2
(非零目標下 的根)
設 ,其中 、。同餘式 有解當且僅當 為偶數且 是模 的平方。此時它恰有 個模 的根,而且每個根都滿足 。
證明
(賦值、縮小的模數與提升)
根的賦值。 若 ,則 且 ;否則 整除 ,因同餘亦整除 ,與 矛盾。兩個小於 的賦值必須相等:若不同, 的賦值會等於較小者,與它可被 整除矛盾。故 ,所以 必為偶數,設為 ;若 為奇數便沒有解。
簡化條件。 當 ,寫 ,其中 。除以 後得到等價的簡化條件
除法改變了模數,不能保留模 直接約去。
單位方程。 若 模 不是平方,由於 ,便沒有根。若 是模 的非零平方,則對每個 ,單位方程恰有兩個模 的根。事實上模 有兩個根 ,因 為奇數而互不相同。若 是模 的根,其提升 滿足
奇質數模下 可逆,故恰有一個 使提升仍是根;歸納即得結論。
計數。 令 。模 而 的剩餘類 ,經 恰好對應一個模 的單位剩餘類 。因為 ,模 的兩個根各有 個模 的提升,而它們都是簡化條件的根。因此原同餘恰有 個根。
證明透視
假設在計數中何處介入
證明只有一個不顯然的步驟:除以 之後, 的條件只在模 下成立,但根 只由 模 決定。中間相差的 個 的冪是自由的,計數中的因子 正是由此而來。
假設 只用了一次:排除平方可被 整除的根,使目標能夠決定每個根的賦值。 為奇數則用了兩次:使模 的兩個根互不相同,並使 可逆,從而每個根唯一提升。若沒有這個假設,連單位目標的計數也會失效:模 時, 有 四個根,而不是兩個。
零目標
定理 6.2.3
( 的根)
的根恰好是可被 整除的剩餘類,包括 ,共有 個。
證明
(平方的整除條件)
對 , 即 ,亦即 ;零剩餘類亦是根。模 下可被 整除的剩餘類共有 個。零不能透過指定小於 的有限賦值 來處理。
例子
例題 6.2.4
( 的六個根)
這裏 、、、、。令 ,簡化條件是 ,其根為 。每個根有三個模 的提升: 與 。乘以三得到模 的六個不同根:
例如 。數量 證明列表完整。相反, 沒有解,因目標的賦值是一。
例題 6.2.5
(賦值為偶數但單位部分不是剩餘)
考慮 。這裏 ,所以 、、,賦值檢驗通過。寫 並除以 ,得 。模 的平方只有 與 ,所以沒有根。定理的兩個條件缺一不可:賦值為偶數,而且單位部分是平方。
例題 6.2.6
(模 的零目標)
對 ,有 、,所以根是 的倍數:
共有 個。例如 ,但 。這個數目是奇數,所以不可能來自非零目標的成對計數 。
常見錯誤
反例模式
縮減目標後不能保留原模數
聲稱: 的根,是 而 。後者只有 與 兩個根,給出 與 。但 ,而 。這個說法漏掉了六個根中的四個。除以 時模數亦須一併除以 :正確的條件是 。
常見錯誤
(兩個根只是單位目標的數目)
模奇質數冪時,單位目標的根數是零或二。對賦值為 的非零目標,根數是 : 有六個根,不是兩個。只找到 兩個根便停下,會漏掉其他提升。
常見錯誤
(把零目標當作賦值為 )
把 代入非零目標的公式並不成立。對 ,它會給出 個根,但正確數目是 。
練習
快速檢查
( 有多少個模 的根?)
解答 · 答案
根是 的倍數,共 個剩餘類。
快速檢查
( 有解嗎?)
解答 · 答案
沒有。目標模 非零,賦值為奇數 ,但根必須滿足 。
快速檢查
(求 的所有模 根。)
解答 · 答案
寫 ,則 ,故 。取模 的 ,得 ,根為 ,即 個根。
快速檢查
(為何單位根的提升論證需要 為奇數?)
解答 · 答案
只有 為奇數時,單位根的 才模 可逆。 時因子二不可逆,唯一提升的證明不適用;模 時 有四個根。這本身並不分類二的冪次模數的情況。