動機
模質數的多項式根,只是更高質數冪根可能有的第一位。有時下一位被唯一決定,有時每一位都可用,有時全不可用。導數描述這個分別,但重要的是模質數的導數類,而非實數微分性。
先前平方同餘章處理特定多項式及其特殊奇異情形。這裏證明任意整係數多項式的單步規則,令有限提升樹列出指定質數冪精度的全部根。相容無限路徑帶來 進整數;由相容剩餘類定義它們,可不假設實數收斂或尚未發展的 進域理論而證根定理。
設 為任意質數,包括二,。若 ,形式導數為 。一般單根定理不要求根非零,也不要求質數奇,關鍵是導數模 非零。
定義
定義 10.1.1
(提升、單根與奇異根)
選整數代表 後,模 的根有 個候選提升 ,模 ,。若 ,其模質數根稱為單根,否則稱奇異根。導數類只依賴 模 ,所以沿分支保持此狀態。
提升樹第 層是模 的根,每根連到下一層約化回它的根。高層根必約化成低層根,不同父類的子根列表互不相交。
定義 10.1.2
(相容剩餘類定義的 進整數)
由序列 構成,其中 且 。逐座標加乘;因約化是環同態,結果保持相容。
等價地,每元素有唯一 進位數字 ,,首 位給 模 。無限數字式表示相容有限截段,不是按實絕對值計算無限和。整數剩餘類給嵌入 ,因非零整數不可能被每個 整除。
對 ,逐座標定義 。其為零恰好在每個 都模 為零時,所以此環的根正是多項式根的一條相容無限路徑。定義沒有把 進整數識別為普通實數。
定理
定理 10.1.3
(列盡下一位的提升規則)
若 ,令 。候選 為模 根,恰好在
導數模 非零時恰一個子根;導數零且 零時全部 個子根;導數零但 非零時沒有子根。對每個 均成立,包括 。
定理 10.1.4
(相容根與單根 Hensel 提升)
每個模 單根,在每個更高有限精度及在 中,都有唯一保留首類的提升。一般地, 在 有根,當且僅當每個模 都有根,即使最初未把那些有限根選成相容。
是特徵零整域,元素可逆恰好在首個模 類非零時。奇異根未必有唯一子根,也未必有唯一無限延續。
證明思路
導數來自精確多項式恆等式
證明
(精確展開與一條線性同餘式)
二項式定理給整係數多項式 ,使
因每個 中, 次數零及一的項為 、,其餘全含 。沒有除以二或任何階乘,所以質數二也適用。
取 ,由 ,最後項模 消失;首兩項為 ,得到同餘。非零導數在質數域有唯一逆,故恰一個 ;零導數則不是恆等零等於零,就是非零常數等於零,分別容許全部或不容許任何 。這是全部情形的證明,沒有把奇異根排除在算法外。
由模 全部根起步,反覆規則便枚舉任意指定 的全部根。每個下一類都具所述形式,父類互異,所以歸納保證列盡且無重複。若 約化為非零多項式,初始根數受其約化次數限制;若全部係數被 整除,則約化為零多項式,每個類起初都是根,不能對零約化套次數界。這個有限枚舉不代表對很大精度或輸入已證高效率。
證明透視
為甚麼一條精確恆等式就處理所有情況
關鍵一步是恆等式 ( 為整係數),並取 。假設 只透過 用上:它使二次項模 消失,剩下一個對唯一未知數位 為線性的同餘式。在域 上的線性性產生三分情況:係數為單位時恰有一解;係數為零時按 而定,或全部是解,或沒有解。由於沒有除以任何階乘,論證對所有 一致成立,包括 。
單根分支只有一條無限延續
證明
(被迫的選擇與有限分支)
整係數多項式評值保持同餘,所以單根的導數類沿提升一直非零。每層恰有一個子根,構成相容序列,按定義便是 進根。反過來,保留該首類的任意 進根,每層都須用同一被迫選擇,故必相等,不需實數大小的極限論證。
任意奇異分支若每個有限層都有根,仍能選出相容路徑。首層有限,若可到任意高層,至少一首根有任意高層後代,否則有限多個有限高度界會界住全樹。其有限個子根中,再有一個保留無界後代性質,反覆選下去,得到相容根及 進整數,令 每座標為零。反方向直接約化即可。這個有限分支論證,是把各層分開存在變成單一相容解所缺的一步。
證明透視
每層存在還需要相容性論證
不相關有限根的集合本身不是 進整數。單根由唯一提升提供相容;奇異情形則用有限分支,選仍可到任意高層的子根,反覆構造路徑。幾次成功提升或看似固定的有限數字圖樣,都不證明每層存在。
單位、首個非零位與沒有零因子
證明
(逐層求逆與第一個非零數位)
首類非零時,每個 模 都可逆;逆唯一,所以相鄰層逆互相約化,形成 的乘法逆。首類零時不可能有逆,因等於一的乘積約化模 會矛盾。
非零 進整數有首個非零位,設位置 。移位數字給 , 為單位;它模 是非零的 倍數,確非零。若 也非零,則乘積 中 是單位,首個非零位為 ,乘積非零,證明整域性。特徵零來自已證整數嵌入,所以剩餘特徵 不令整個環特徵也變 。
這也說明有限根數與相容無限根數可不同。整域中非零多項式的線性因子不能任意相消,有限商環卻可有零因子,下面二處例子會具體展示。
例題
例題 10.1.5
(五處唯一提升的立方根)
對 ,測五個類只有三是根;導數 模五為二,所以單。 時 , 為零,根為模二十五的三。 時 一,修正 給 二,根為模 125 的 。驗算 ,往後數字亦唯一。五十三是該精度同餘類,不表示按普通絕對值接近實立方根。
例題 10.1.6
(四個有限二冪根,卻只有兩個無限根)
在二處首根一為奇異,子根為模四的一、三,再到模八全部四個奇數類。下一步三與五的 奇,沒有子根;一與七各有兩個,得到模十六根 。
在 ,由 及整域性知只能 ,兩者都確是根。它們不同,因環特徵零,雖然模二都為一。每個充分高有限層有四根,不會給四個無限根,因部分有限分支終止。僅奇異性本身,不能決定最終根集是空、一個或多個。
例題 10.1.7
(模質數有根卻沒有下一位)
對 ,模 唯一根零,導數也零,但 模 非零,所以沒有模 子根,也沒有 進根。這吻合先前平方同餘的奇賦值障礙,現由一般多項式規則得到。模質數可解本身不能證更高精度存在。
常見錯誤
常見錯誤
(單根指導數非零,不是根非零)
單根指模 導數非零,不是根本身非零。二處多項式若導數奇,仍唯一提升。不需在 Taylor 式除以階乘,那反會遮蔽二進情形。
常見錯誤
(各層的有限根還不是 進根)
奇異根的直接子根是全有或全無,但不同子根在更高層可有不同行為。 進根是相容無限序列,不是每層任選一根。若沒有別的論證供應,有限計算不能證明全部層都有根。本章證單根定理及完整單步奇異規則,不宣稱一般強賦值版本 Hensel 定理或任意奇異樹的閉式分類。
反例模式
沒有單根條件,提升可能失敗或分岔
命題:每個模 的根都唯一延伸為 中的根。取 、。剩餘類 是模 的根,但 ,而 是奇數,所以單步規則不給出任何子根。直接驗算: 與 模 都是 。存在性失敗。對 ,模 的根 同樣是奇異根,它在 中有例題求得的兩個延續 與 ,所以唯一性也失敗。修正後的敍述須假設 。
小結
精確二項式展開把下一位化成線性同餘,子根恰一個、全有或全無。單根給唯一相容 進根,有限分支證一般每層存在判準。相容剩餘類還給單位及整域性質,區分有限同餘與無限 進解行為。
練習
快速檢查
(把模七 的根三提升到模 343,找同精度另一根並證列盡。)
解答 · 答案
首步 一、導數模七六,故 給 一,根為模四十九的十。再有 ,導數二十模七六,故 二,根為模 343 的 。相反根 235。模七只有三、四兩根,均單,故兩唯一分支已列盡。精確驗算 。
快速檢查
(用單根提升及多項式分解,求 模 27 及在 中全部根。)
解答 · 答案
模三根為零、一、二,導數 恆模三負一,故各自唯一提升。整數根 已提供三分支,所以模 27 根為 。在 中恰為 ;分解 配合整域性也給同一完整答案。
快速檢查
(對奇 ,追蹤 由模 到 的根,計第三層根數並說明哪些第二層分支終止。)
解答 · 答案
首根零有 為 ,故全部 個子根 模 出現。下一步 ,導數 模 零,所以只有 有子根,各有 個。奇 令兩父類互異,共 個模 根,其餘第二層分支都終止。與非單位平方根分類一致,這裏由一般規則推得。
快速檢查
(證明相容截段 定義 中 的逆,解釋 及為何不是普通實級數收斂。)
解答 · 答案
第 部分和乘 得 ,模 為一;部分和相容,故定義 進逆。 時數字全一,第 類為 ,恰是整數負一的相容類,也確實是自身逆。部分和按實絕對值無界,此式表示相容同餘,不是實幾何級數收斂。