动机
整数 Euclid 算法与多项式长除法有相同的结构作用:把问题化为余式较小的问题。前面的章节分别在整数及域上多项式使用这个机制。现在把真正需要的假设抽取出来,再问:若不能作余式递减的除法,哪些结论仍成立?
三类整环组织了答案。Euclid 整环有整数值大小控制的除法;主理想整环要求每个理想只有一个生成元;唯一分解整环要求非零元素可分解为不可约元,并有唯一性。定义记录的是不同信息。它们之间的蕴含需要证明,而熟悉的分解外观,不是任意整环同时属三类的证据。
本篇整环均为交换环,有 且无零因子。使用前篇的理想、单位及多项式次数。两元素相差单位因子时称为相伴;分解唯一性必须容许这个不确定性。
定义
定义 5.1.1
(三种整环条件)
Euclid 整环是具有函数 的整环,对任意 、,存在 使 ,且 或 。主理想整环(PID)要求每个理想均由一元素生成。唯一分解整环(UFD)要求每个非零非单位都有有限不可约分解,且除了因子次序及相伴外唯一。
此处 Euclid 定义只要求所示余式条件,不要求大小乘法性,也不另加元素与其倍数之间的大小比较。整数用 ,域 上的 用次数。域本身亦包括在内:取常值大小零,除法余式总为零。
定义 5.1.2
(不可约元与素元)
非零非单位 若满足每次 都有一个因子为单位,称为不可约元。若 总蕴含 或 ,则称为素元。 的最大公因子 整除两者,且每个公因子都整除 ;它只在相伴意义下确定。
整环的素元必不可约。若 ,素性给出例如 ,故 ,消去非零 得 ,所以 为单位。反方向须额外结构,会成为 PID 的重要结论。“尚未找到分解”既没有证明不可约,也没有证明素性。
概念视角结构
把整除读成主理想的包含关系
在整环中, 当且仅当 ; 是单位当且仅当 ; 相伴当且仅当 。用这种语言,非零非单位 不可约,当且仅当 在真主理想中是极大的; 是素元,当且仅当 是素理想。分解问题于是转化为关于主理想这一有序集合的问题。在 PID 中,这个集合包含所有理想,所以下面的链论证和极大性论证才能使用。
定理 / 命题
定理 5.1.3
(Euclid 除法推出主理想与 Bézout)
每个 Euclid 整环都是 PID。在 PID 中, 由最大公因子 生成,并有 使 。特别地, 互素当且仅当 。
定理 5.1.4
(主理想推出唯一分解)
PID 的每条上升理想链均最终稳定。PID 的每个不可约元都是素元,每个非零非单位都有不可约分解。因此每个 PID 都是 UFD,且
证明思路或证明
证明
(最小大小给出生成元)
取 Euclid 整环的非零理想 。其非零元素大小构成非空非负整数集,故有最小值,取达到它的 。任意 除以 ,余式 仍在 。若非零,其大小较小,矛盾。因此每个 都是 的倍数,。零理想是 ,故得 PID。
在 PID 写 。由 , 整除两者;由 ,它是两者的 线性组合。每个公因子都整除此组合,故 是最大公因子。一输入为零时论证仍成立;两者均零时生成元为零,不把它称作单位或不可约元。最大公因子是整除命题,Bézout 等式则是理想成员命题,PID 性质在此把两者连起来。
理想链取代数值下降
证明
(上升链与分解的存在)
设 为 PID 的上升理想链。并集 是理想:任取两元素,它们同在某个足够后的理想内,该处对加法与标量乘法封闭。写 。由 ,它已在某个 ,于是 ,故相等,之后全部相同。无需 Euclid 大小函数,便证明上升链条件。
假设某非零非单位 没有不可约分解。它不是不可约,故可写 ,两者均非单位。至少一因子也没有不可约分解,否则把两个有限分解相乘便能分解 ;把该因子命名为 。此时 :整除给包含;若相等,则 ,消去得 ,与非单位矛盾。重复会产生严格上升的主理想链,违反链条件。所以不可约分解必存在。
这使用可逐次选取的通常集合论背景。亦可用上升链条件,在反例生成的主理想中选极大者,分解后反驳极大性。障碍是无限严格增大的理想链,并非声称任意环元素都有递减的数值大小。
为何不可约元变成素元
证明
(不可约元是素元,以及唯一性)
设 PID 中 不可约,且 、。 的生成元 整除 ,故不可约性迫使 为单位或与 相伴。后者会使 ,矛盾。故 为单位,缩放其 Bézout 等式得 。乘 后, 均被 整除,所以 ,证明素性。
对唯一性,比较非零元素的两个不可约分解。一边的第一因子整除另一边乘积,反复用素性便知它整除某不可约因子,两者遂相伴。消去匹配的非零因子后重复,有限过程最后只余单位。非空的非单位乘积不可能为单位,因为交换环中若乘积可逆,每因子均可逆。因此两列长度相同,按重排及相伴逐一匹配。存在性与唯一性用不同论证,两者对 UFD 结论均必要。
证明透视
两种不同的停止理由
Euclid 除法因非负整数大小下降而停止;PID 分解因理想不能永远严格上升而停止。从 Euclid 整环转到 PID,即使没有指定大小函数,仍保留第二机制。混淆两者,便会暗中把 Euclid 假设加进所有 PID 的定理。
例题详解
例题 5.1.5
(Gaussian 除法与最大公因子证书)
在 定义 。对非零 ,把 的两实坐标各四舍五入至最近整数,得 Gaussian 整数 。则 ,所以非零余式满足 ,故此范数为 Euclid 大小。
取 、,得 ,再有 。最大公因子是单位,回代给 。两次余式范数均下降,最后等式亦可独立验证互素。Euclid 证明现在保证整个环的理想主性与唯一分解,而非只处理这两个输入。
例题 5.1.6
(最大公因子未必生成二元素理想)
在 , 为真理想,因为每元素常数项均零。若它是 ,则 整除 。把它看成系数在整环 的 多项式, 的因子在 的次数为零,故 。它在该环整除 ,所以为单位或与 相伴;后者不可能整除 ,令 即见。因此每个公因子都是单位,任何候选理想生成元都为单位,与真理想矛盾。两元素最大公因子为一,但环内不存在 。仅凭最大公因子存在,不能把 Bézout 结论推到任意整环。
例题 5.1.7
(不可约却不素的元素)
令 。范数 具乘法性,单位恰为 。没有范数二或三的元素: 时至少五, 时是平方。
二、三的范数为四、九,若分解为非单位,便须有范数二或三的因子,故两者不可约。 的范数为六,非平凡分解须有范数二与三,也不可能,故亦不可约。然而
给出不等价不可约分解:两边因子范数不同,而相伴保持范数。二整除右边乘积,却不整除任一因子,因其整数系数一为奇数。因此离开 PID 论证后,不可约未必素;此整环不是 UFD、不是 PID,也不是 Euclid 整环。
使用层级而不反转箭头
要证具体环是 UFD,若较强条件容易建立,证它已足够。Gaussian 坐标取整证 Euclid 除法,余下两结论由结构定理完成。反之,要否定 PID,须展示非主理想,或用不具唯一分解等合法障碍。找不到方便大小函数,不是非 Euclid 的证明。
定理给蕴含而非定义等价,未分类全部 Euclid 函数,也未证每个 UFD 都主理想,不能把箭头倒画便宣称反向。即使有求最大公因子的算法,仍须检查它保证什么:算出公因子不自动把它表为线性组合,多项式例子已展示这个区分。
常见错误
常见错误
(三种条件都假定整环)
三种定义均假定整环。零因子环中,非零因子可能不能消去,而素性及唯一性证明都在关键位置使用消去。Euclid 大小亦非要求每个代数操作均使其下降,只要求选定的非零余式较小。
反例模式
消去失效时,素元未必不可约
没有整环假设,“素元必不可约”就不成立。在 中,剩余类 是非零非单位,而且是素元:模六的剩余类有确定的奇偶性, 为偶数当且仅当 或 为偶数。然而 给出 ,而 与 都不是单位,因为它们的倍数全是偶数。在“素元必不可约”的证明中,现在 以 、 成立,但消去 会得到 :这里 ,而 。在整环中这一步消去合法,蕴含关系便成立。
常见错误
(不可约与素是不同条件)
不可约限制每次分解必有单位因子;素性控制乘积整除。在已证为 PID 的环中两者相同,但在任意整环把它们当同义,便抹去二次整数反例。唯一性也须保留单位及相伴: 的单位为 ,只选正负号不能消除所有不确定性。
总结
最小余式大小使每理想主性成立。主理想给 Bézout 等式及上升链稳定,再给不可约元的素性、分解存在与唯一。Gaussian 整数展示成功链;二变量多项式及二次整数则指出较弱信息不足以推出哪些结论。
练习
快速检查
(证明整环中同一对元素的任意两个最大公因子相伴,并另处理 。)
解答 · 答案
两个最大公因子彼此整除。若非零,写 、,消去得 ,故相伴。对 ,最大公因子须被每个公因子整除,包括零,因此必为零;两者就是同一零元素,无需消去。
快速检查
(在 PID,证明非零非单位 为素元当且仅当 为非零素理想,并证不可约元生成极大理想。)
解答 · 答案
对非零非单位 , 蕴含 或 ,正是素元定义;非单位保证理想真。若 不可约且 ,则 ,故 单位或与 相伴,所以 或 ,证明极大性。单位的理想为全环,不符合真素理想条件。
快速检查
(在 验证 、,并用范数证三个所示因子不可约。)
解答 · 答案
直接相乘得 、。三因子范数为二、五、五,均为正有理素数。范数乘法性迫使每次分解有范数一的因子,即单位,故不可约;相伴仍可相差任一 Gaussian 单位。
快速检查
(证明 的理想 为真理想且不主。)
解答 · 答案
映射 是环同态,因为关系 模二变成 。核恰为指定理想:若 偶,原元素为 ,末项偶。因此理想真。若为 ,则 整除二与 ,所以 同时整除四、六,只可能为一或二。二不可能,一会使 可逆、理想等于全环,矛盾。因此不主。