动机
模质数的多项式根,只是更高质数幂根可能有的第一位。有时下一位被唯一决定,有时每一位都可用,有时全不可用。导数描述这个区别,但重要的是模质数的导数类,而非实数微分性。
先前平方同余章处理特定多项式及其特殊奇异情形。这里证明任意整系数多项式的单步规则,令有限提升树列出指定质数幂精度的全部根。相容无限路径带来 进整数;由相容剩余类定义它们,可不假设实数收敛或尚未发展的 进域理论而证根定理。
设 为任意质数,包括二,。若 ,形式导数为 。一般单根定理不要求根非零,也不要求质数奇,关键是导数模 非零。
定义
定义 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 根为 。在 中恰为 ;分解 配合整域性也给同一完整答案。
快速检查
(对奇 ,追踪 由模 到 的根,计第三层根数并说明哪些第二层分支终止。)
解答 · 答案
首根零有 为 ,故全部 个子根 模 出现。下一步 ,导数 模 零,所以只有 有子根,各有 个。奇 令两父类互异,共 个模 根,其余第二层分支都终止。与非单位平方根分类一致,这里由一般规则推得。
快速检查
(证明相容截段 定义 中 的逆,解释 及为何不是普通实级数收敛。)
解答 · 答案
第 部分和乘 得 ,模 为一;部分和相容,故定义 进逆。 时数字全一,第 类为 ,恰是整数负一的相容类,也确实是自身逆。部分和按实绝对值无界,此式表示相容同余,不是实几何级数收敛。