环论
前置知识:抽象代数基本概念 、群论
引入
环论 (ring theory)研究形形色色的环。
本文涉及的环论的内容,与数论中的整除理论密不可分。首先,类似群论中的正规子群,本文首先介绍环同态的核,它称作环的理想;其实,这是数论中的数的概念在一般环的推广。然后,考虑将整数环上的素数、辗转相除法、质因子分解等概念推广到一般的环上,就有了不同类型的整环的概念。
数论中的很多结论在其它常见的环上,都依然成立。可以说,环论的一部分工作,就是在讨论使得这些数论中的结论在一般的环上能否成立;如果不能,需要给环施加怎样的限制才能够使这些结论成立。
记号
在不引起歧义时,本文可能会省略掉环的乘法记号,并且会将环 写作环 。环 中,加法单位元也称作零元,记作 ;乘法单位元也称作幺元,记作 。
本文的环的定义不要求有幺元
注意,本文的环的定义不要求含幺。有些文章要求环的定义含幺,则本文部分结论的叙述需要稍作调整。比如说,本文中理想可以基于子环定义,但是其它文章中可能需要基于加法子群定义。
理想
类似群的情形,可以建立子环和环同态的概念。
子环
对于环 和它的子集 ,如果 也是一个环,则称 是 的 子环 (subring)。
例子:整数环
对于任何整数 ,都有 是 的一个子环。
环同态
对于环 和 ,如果 保持环的加法和乘法运算,即对所有 都成立 和 ,则称映射 是自环 到环 的 同态 (homomorphism)。
环的定义要求含幺的情形
如果环的定义要求含有幺元,那么,环同态的定义也常常要求将幺元映射至幺元。对于非零幺环间的同态来说,这个额外的要求仅仅是保证了同态不会将整个幺环映射到零元。
例子:整数环 (续)
对任何非零整数 取模的映射,即 ,其中, ,都是环同态。
对群同态的核和像的 讨论 可以几乎原封不动地搬到此处。同态的像的(相对)大小决定了同态是否是满射,而同态的核的平凡与否则决定了同态是否是单射。环同态的核定义如下:
同态的核
自环 到环 的同态 的 核 (kernel)是 ,记作 ,其中, 是 的加法单位元。
显然,环同态的核和像都是子环。反过来,并不是所有子环都可以成为某个环同态的核。能够成为环同态的核的子环称为环的理想。
理想
对于环 和它的子环 ,则称 是 的
左理想 (left ideal),如果对于所有 ,都有 ,这里, ;
右理想 (left ideal),如果对于所有 ,都有 ,这里, ;
理想 (ideal),如果 既是 的左理想,也是 的右理想。
这里要求理想 对环 的左乘和右乘都封闭。这个条件是自然的。因为,理想中的元素在环同态中会映射到零元,而任何数左乘或右乘以零都应该等于零,这就是所要求的封闭性。除此之外,因为环的加法结构是 Abel 群,任何子群都是正规子群;而环的乘法结构又十分原始,不会对子结构施加额外的限制。这就说明,对左乘和右乘封闭这个条件也是充分的。
例子:整数环 (续)
作为例子,前面提到的子环 其实是 的理想。它是所有 的倍数构成的集合。一个 的倍数,与任何整数相乘,都会得到 的倍数。事实上, 的全部理想都是这样的形式,这样的环称为 主理想整环 。对于一般的环,有些理想并不是某个元素的倍数的集合;这样的一般的环的存在,也正是研究理想(而不是简单地研究倍数)的最初动机 。
商环
和群一样,基于环的理想,可以在全体(加法群意义上的)陪集的集合上定义 商环 (quotient ring)。考虑集合
这里,陪集 。可以证明当且仅当 是理想时,运算
是良定义的,即这些运算的结果和陪集中代表元的选取无关。在这些运算下, 构成环。再次和群的情形一致,可以建立环的 第一同构定理 (first isomorphism theorem),并存在环到其商环的自然同态。这些证明,环的理想和群的正规子群,在相应结构的同态中起到了一样的作用。
第一同构定理
设 是自环 到环 的同态,则 是 的理想,且 是 的子环。
自然同态
对于环 和它的理想 ,则由 给出的映射 是自 到 的满同态,称为自环 到商环 的 自然同态 (natural homomorphism)。
例子:整数环 (续)
作为例子,整数模 的同余类构成的环 是 模它的理想 得到的商环。这也解释了符号 的含义。上面提到的模 的映射 就是这里提到的自然映射,相应的核正是理想 。
在环的情形,同样成立其他同构定理。
第二同构定理
设环 有子环 和理想 ,那么 同样是 的子环,而 是 的理想, 是 的理想,并且 。
第三同构定理
设环 有理想 且 ,那么 也是 的理想,并且 。
对应定理
设环 有理想 ,则全体包含 的环 的子环 和商群 的全体子群 之间存在双射 ,它将 映射至 。这个双射保持子环的包含关系,且环 的理想总是映射到 的理想。
这些定理在后文中讨论环和理想的结构时将起到基础的作用。
理想的运算
环的理想上可以定义各种运算。这类似于整数的整除结构上可以定义最大公约数、最小公倍数等概念。
理想的运算
设环 有理想 ,可以定义如下运算:
理想的 和 (sum): ;
理想的 乘积 (product): ,即全体 形式乘积的有限和构成的集合;
理想的 交 (intersection): 。
容易验证,这些运算的结果都依然是环的理想。
例子:整数环 (续)
考虑整数环 的情形。对于理想 和 ,可以得到
一般地,对于环 和它的理想 和 ,总有
利用这些定义,可以将整数的中国剩余定理推广到一般的环上。但在此之前,还需要进一步将诸如素数和互素等概念推广到一般的环上。
极大理想
通过环的理想的结构,可以理解环的性质。
非零环 总有两个平凡的理想,即 和 。如果环 还是交换的,那么只有这两个理想的环能且只能是域 。
定理
设 是交换的非零幺环,那么 是域,当且仅当 只有平凡理想 和 。
证明
如果 是域,则对于任何非零理想 都可以任取非零元素 ,于是,任何域中的元素 都有 ,故而 。反过来,对于任何 且 ,可以验证 是理想,它必然等于 ,因而存在 使得 ,这就说明 存在逆元,故而有 是域。
这里交换环的条件是必要的;不然,需要同时限制左理想和右理想都是平凡的,才能保证环是除环。
这里的结论可以推广到环本身不是域的情形。但是,此时需要转而考虑商环,讨论交换非零幺环的商环是域的条件。商环 是域,这意味着商环 中只有平凡理想,根据对应定理可知,原来的环 中没有严格介于模掉的理想 和原来的环 之间的理想。这样的理想 称为极大理想。
极大理想
对于环 和它的理想 ,如果 ,且包含 的 的理想只有 和 两个,则称理想 是一个 极大理想 (maximal ideal)。
定理
设交换非零幺环 有理想 ,那么商环 是域,当且仅当 是极大理想。
例子:整数环 (续)
例如,整数环 中的理想 是极大理想,当且仅当 是素数。对于素数 ,商环 是域,也记作 。
并不是所有的环都有极大理想,但是非零幺环中总是有极大理想。
定理(Krull)
对于非零幺环 的理想 ,总有 的极大理想 使得 成立。
证明
思路是利用 Zorn 引理。考察全体包含 的 的真理想(即不等于 的理想)的集合 。因为 ,它非空,且在包含关系下形成偏序集。对于其中的任何链 ,设它们的并集为 ,则容易验证这也是理想。而且, ,否则 ,亦即存在 使得 ,这与 是真理想相矛盾。由此,依 Zorn 引理,存在极大理想 。
极大理想,类比到整除理论中就是不可约元。这是因为,理想的包含关系就是整数的整除关系;没有作为超集的理想,就相当于没有可以除尽的因子。但是,极大理想的概念比不可约元更为宽泛,这是因为并不是所有的理想都是主理想。
素理想
域的条件比整环的更为苛刻。能够确保商环是整环的理想称为素理想,它类似于整除理论中的素数的概念。
素理想
对于交换环 和它的理想 ,如果 ,且对于环中任意元素 ,每当 成立时总有 或 ,则称理想 是一个 素理想 (prime ideal)。
这个定义看起来稍显突兀,但是对比素数的定义,这个素理想的定义也是自然的。
定理
设交换非零幺环 有理想 ,那么商环 是整环,当且仅当 是素理想。
证明
对于交换非零幺环 ,商环 是整环,当且仅当 没有零因子。将陪集 记作 。商环 没有零因子,就等价于 总能推出 或 。根据对应定理,这就等价于 总能推出 或 。
在整数环 中, 是极大理想和素理想,当且仅当 是素数。在一般的交换环中,极大理想总能推出素理想,当然反之未必成立;这从它们对应的商环的性质上可以看出来。
定理
对于交换非零幺环 ,那么它的极大理想必然是素理想。
稍后要看到,只有在那些具有良好性质、足够与整数环相似的环中,逆命题才成立。
主理想
类似子群的概念,在环的讨论中也常需要考虑由某个子集生成的理想。
由子集生成的理想
对于非零幺环 和它的非空子集 ,如果 是包含 的 的理想中(依包含关系)最小的,则理想 称为 由子集 生成的理想 (ideal generated by a subset),并记作 。此时, 称为 的 生成子集 (generating set)。
主理想
由单个元素 生成的理想称为 主理想 (principal ideal),记作 。此时, 称为 的 生成元 (generator)。
对于集合 ,可以给出其生成的理想的构造。首先,有如下定义
其实它们分别是 生成的左理想和右理想。然后,由子集 生成的理想就是 。对于交换环,定义出来的这些结构都相同。
整数环中的所有理想 都是主理想,下文中常记作 。
整环
整环是交换、含幺、无零因子的非零环。这个概念正是整数环的推广。但是,这样得到的环性质未必足够好到允许将整数的整除理论中的每个结论都原样照搬过来。为了能够推广数论中的结论,可以在整环上进一步作出限制。其中,最为常见的三种整环分别是欧几里得整环、主理想整环和唯一分解整环;前面的概念严格地包含在后面的概念中。
整除关系
首先,这里将整数的整除理论中的相关概念推广到一般的交换环上。
整除
设交换环 有元素 ,如果存在 ,满足 ,则称 整除 (divide) ,记作 。此时称 是 的 因子 (divisor)。
相伴
设交换环 有元素 ,如果它们只相差了一个可逆元,即存在可逆元 ,满足 ,则称 和 是 相伴的 (associate)。
整除关系是环上的 偏序 关系,而相伴关系是环上的等价关系。从理想的角度看, 等价于 , 和 相伴等价于 。因而,在讨论环中的元素时,通常不计较相伴元之间的差异。和整数的情形类似,交换环中 和 的最大公因子就定义为 的下确界。
最大公因子
对于交换环 和它的元素 ,如果存在非零元素 ,它满足 和 ,且对于任何满足 和 的 都成立 ,则称 是 和 的 最大公因子 (greatest common divisor),记作 。
在整环中,最大公因子在相伴意义下是唯一确定的。下面的讨论就限制在整环中。
整环中还可以建立类似素数的概念。在整数理论中,素数存在着两个等价的定义,但是在一般的整环中,这两个定义对应着不同的概念:
素元
设整环 有非零元素 ,如果 是素理想,也就是说, 总能推出 或 ,则称 是 素元 (prime)。
不可约元
设整环 有非零元素 ,如果 不是可逆元,而且对于任何 且 都有 或 是可逆元,则称 是 不可约元 (irreducible),或称 不可约。反过来,如果 且 都不是可逆元,则称 可约。
可以说明,不可约元 对应的主理想 一定是环的所有主理想中极大的;但是,一般的整环中,并非所有理想都是主理想,所以不可约元和极大理想的概念并不等价。
类似于证明主理想整环中,素理想一定是极大理想,一般地可以证明如下结论:
定理
设 是整环,如果 是素元,那么 也一定是不可约元。
证明
设 是素元,且 满足 。因为 是素元,不妨设 成立,则 。因为整环上成立消去律,有 ,故而, 有逆元 。这就说明 是不可约元。
反过来,这一结论并不成立。
反例
在二次整数环 中, 是不可约元,但是 ,所以它不是素元。
这里给出这一反例的证明,不熟悉二次整数环的读者请先阅读 二次整数环 部分。设 是二次整数环上的范数。对于任何分解 都有 。如果 都不是可逆元,则 和 都大于 ,因而必然有 。但是 上没有这样的元素,亦即 没有整数解。这就说明 是不可约元。至于 不是素元,就是要证明 不能整除 ,这显然。
欧几里得整环
相关阅读:(扩展)欧几里得算法 、裴蜀定理
欧几里得整环是允许做辗转相除法(即欧几里得算法)的整环。
欧几里得整环
对于整环 ,如果存在映射 ,满足 ,而且对于任意 ,其中, ,都存在 使得 成立,这里, 或 ,则称整环 为 欧几里得整环 (Euclidean domain, ED)。映射 称为欧几里得整环中元素的范数(norm)。
这个定义其实就是整数中的带余除法的推广。范数的存在使得能够衡量余数和除数的相对大小。这样在辗转相除的时候,对应的余数的范数也在不断下降;因为范数取值在自然数上,这样的过程必然结束在 时。这样,就得到了欧几里得整环上的辗转相除法。
能够做辗转相除法,这意味着欧几里得整环上能够高效地计算最大公因子。完全类比整数的整除理论,可以证明,辗转相除法的结果一定是最大公因子,而且裴蜀定理成立,其中的系数可以通过扩展欧几里得算法确定。
定理
对于欧几里得整环 和它的元素 ,对 和 做辗转相除法的得到的结果 是 和 的最大公约数,且存在 使得 成立;反过来,任何 形式的元素都是 的倍数。
注意到,在环论的语言中,所有形如 的元素正是理想 中的元素,而这一定理就说明了 一定是主理想 。
其实,欧几里得整环中的理想一定是主理想。
定理
欧几里得整环中的理想一定是主理想。
证明
设 是欧几里得整环,且 是它的理想。如果 ,它显然是主理想。设 是非零理想。依定义,环 上有范数 ,于是可以取 中范数最小的非零元素 。此时,对于任何 ,都有 满足 或 。又因为 ,所以依 的选取方式就可知 ,也就说 。这就说明 必然是主理想。
主理想整环
所有理想都是主理想的整环叫做主理想整环。这是性质相当良好,也十分常见的一类整环。在这些整环中,环中理想的概念就等同于整数中倍数的概念。
主理想整环
对于整环 ,如果它的每个理想都是主理想,则称它为 主理想整环 (principal idel domain, PID)。
因而,上一节最后一个定理就可以复述如下:
定理
欧几里得整环一定是主理想整环。
在主理想整环中,极大理想就等价于不可约元生成的理想。类似整数中素数和不可约元是等价的,主理想整环中,这两个概念也是等价的,故而极大理想和素理想也是完全等价的。
定理
设主理想整环 有非零理想 ,则 是素理想,当且仅当 是极大理想。
证明
只需要证明素理想都是极大理想。设主理想整环 中有非零素理想 ,且同时有理想 满足 。这说明 ,故而存在 使得 。但由于 是素理想, 就意味着 或 。如果 ,就说明 ,故而 ;如果 ,就说明 ,故而 ,又因 ,有 ,即 存在逆元 ,于是 。这就说明, 是极大理想。
推论
设主理想整环 有非零元素 ,则 是素元,当且仅当 是不可约元。
上一节中对裴蜀定理的分析可以迁移到主理想整环上。
定理
设 是主理想整环,且 是非零元素。设 是理想 的生成元。那么, 和 的最大公因子是 ,且在相伴意义下唯一;而且,存在 使得 成立。
也就是说,主理想整环中 裴蜀定理 依然成立。同样是存在最大公因子,欧几里得整环和主理想整环的最大区别在于在前者中,最大公因子可以通过辗转相除法高效地计算,但是主理想整环中一般并没有这样的高效算法。
唯一分解整环
比主理想整环更一般的概念是唯一分解整环。整数的唯一分解定理称为 算术基本定理 。类似的唯一分解定理其实在一些并非主理想整环的整环中依然成立。这样的整环叫做唯一分解整环。
唯一分解整环
对于整环 ,如果任何非零且不可逆的元素 都能写作 的形式,这里的 是可能重复的不可约元,且这样的分解在相伴和重新排列的意义下唯一,则称整环 是 唯一分解整环 (unique factorization domain, UFD)。
算术基本定理说明,整数环 是唯一分解整环。
前文给出了不可约元不是素元的反例,其中涉及的整环 中唯一分解定理不再成立。但是,在所有唯一分解整环上,不可约元和素元都是等价的。
定理
对于唯一分解整环 和它的非零元素 ,则 是素元,当且仅当 是不可约元。
证明
只需要证明不可约元都是素元。对于不可约元 ,如果 ,那么就存在 使得 成立。因为 是唯一分解整环,所以可以对 都做分解成不可约元的乘积。比较左右两边,根据分解的唯一性可知, 必然和 或者 的某个不可约因子相伴,故而 整除 或 中的一个。这就说明 也是素元。
所有的主理想整环都是唯一分解整环。
定理
主理想整环一定是唯一分解整环。
证明
设 是主理想整环,且 不是零元,也不是可逆元。要说明 可以唯一分解为一系列不可约元的乘积,可以分为两步:首先证明分解的存在性,再证明分解的唯一性。
分解的存在性比较自然。如果 已经是不可约元,就不必继续分解;否则,必然存在 使得 且 都不是可逆元。进而,如果 和 都是不可约元,那么也不必继续分解;否则,对 和 中不是不可约元的,可以进一步分解, 也就可以写成更多元素的乘积。由此,只要乘积中不全是不可约元,就可以将分解过程不断进行下去。分解必然在有限步后终止。不然,选择公理保证可以从 中取出无限长的元素链 满足 且 对所有 都成立,且这些整除关系都是严格的,即链中不存在相伴元。用理想的语言说,这对应着严格无穷递增的理想列: ,其中, 。容易验证,这些理想的并 还是理想,因而必然是主理想。令 为主理想 的生成元,因而,存在 满足 。所以, 。这说明,这个严格无穷递增的理想列并不存在,故而上述分解过程必然在有限步内终止。
然后证明分解的唯一性。可以对分解中因子的个数做归纳。归纳的关键步骤在于验证,如果 且 ,则必然有 与某个 相伴。这里需要用到之前的结论:主理想整环中不可约元都是素元。已知 是 中的不可约元,故而它也是素元,所以对右侧的乘积可以归纳地说明,必然存在某个元素 使得 。所以,存在 使得 ,而 是不可约元, 也是不可约元,依定义只能有 是可逆元,故而 与 相伴。这样就可以利用消去律在左右两侧分别消去 和 ,并将两者相差的相伴元乘到任意一个剩余元素上。根据归纳假设,必然有 和 中不可约元个数相等,且在相伴意义下是一样的。定理得证。
最后,最大公因子的存在性在唯一分解整环上依然成立。
定理
设唯一分解整环 有非零元素 ,且它们可以分解成 和 的形式,其中, 是可逆元, 是各不相同的不可约元, 都是自然数,那么,它们的一个最大公约数是 。
这其实说明,最大公因子存在这个性质比唯一分解定理成立还要弱 。
例子:二次整数环
相关阅读:二次域
抽象代数的理解不能离开例子。正是因为费马大定理的研究过程需要研究一类代数整数的性质,才逐渐发展出了今天的环论 。这里讨论最简单的代数整数,即二次整数。这部分的很多结论的证明需要用到复杂的代数数论知识,故而略去。
二次整数 (quadratic integer)指的是二次项系数为一的整系数二次方程 的复根。所有二次整数能且仅能有形式
这里,
其中, 没有平方因子。
分析
根据二次方程求根公式,可以知道这个方程的根一定可以写成
当 是奇数时,这个根可以写作
否则,当 是偶数时,这个根可以写作
从而可以归纳得知二次整数必然有上述形式。
容易验证,对于这样的 ,集合 构成环。这称为 二次整数环 (quadratic integer ring),它的分式域就是二次域 。当 时,所有二次整数都是实数,故而也称作 实二次整数环 ;当 时,除了整数外的二次整数都是复数,故而也称作 虚二次整数环 。
所有二次整数环 都是整环。其中,当 时, (或记作 )也称 Gauss 整数环;当 时, 则称为 Eisenstein 整数环。
对于二次整数 ,可以定义它的 共轭 (conjugate)是 ,其中,
注意,因为 时,二次整数是实数,所以这里的共轭的概念和复数的共轭的概念并不是完全一致的,但它们都是域论中代数元的共轭的概念的特例。共轭的二次整数是同一个整系数二次方程的根。
在二次整数环上可以定义 范数
二次整数的范数一定是整数。特别地,当 时,范数一定是自然数。范数保持乘法结构,即 。
二次整数环中的可逆元(单位)能且仅能是那些范数是 的元素。对于 的情形,这就相当于考虑 Pell 方程 或 的解。对于 的情形,容易验证,除了 Gauss 整数环 中可逆元是 和 Eisenstein 整数环 中可逆元是 这两种特殊情形外,其余的可逆元都只有 。
二次整数环上定义的范数 可以用来证明它是欧几里得整环。对于 的情形,需要使用它的绝对值 来作为欧几里得整环定义中的范数。利用这样得到的范数,能够证明在 时,
或者在 时,
这些整数对应的二次整数环是在模 下的欧几里得整环。但是,欧几里得整环定义中的范数未必是上述定义的范数。比如在 时,相应的二次整数环也是欧几里得整环,但是需要用到别的范数。对于 的情形,可以证明上面给出的情形就是二次整数环中所有的欧几里得整环。
利用更为复杂的方法,还可以判断某个二次整数环是否是主理想整环。可以证明当 时,只有
对应的二次整数环是主理想整环。比较上面的结果,可以知道诸如 的情形提供了主理想整环不是欧几里得整环的例子。当 时,目前尚没有完整的结果。
但是,可以证明,在二次整数环中,唯一分解整环和主理想整环是等价的。上面的结果说明,比如说 就不是主理想整环,因而也不是唯一分解整环。之前已经通过例子实际证明过了它不能唯一分解,即
利用同样的例子,可以说明理想 也不是主理想。稍后会看到,是唯一分解整环但不是主理想整环的一个简单例子是多项式环 。
尽管很多二次整数环并不是唯一分解整环,但是它们都是 Dedekind 整环 。这意味着,所有二次整数环中的非平凡理想都可以唯一分解为一系列素理想之积。但如果二次整数环本身并非主理想整环,这些素理想因子并不一定对应着素元,因而唯一分解定理(即数分解成素数的乘积)不再成立:这也是研究理想而不是数的最初动机。
多项式环
相关阅读:多项式技术简介
在算法竞赛中,时常会遇到多项式的各种运算。多项式的乘法、取逆、取余等运算可以看作数的运算在多项式环上的推广。利用抽象代数的语言,可以更快地理解多项式环上相关运算的性质。
多项式
对于非零交换幺环 ,一个 上的 多项式 (polynomial)是指形式和
其中, ,且对于每个 ,都有 。这些 称为多项式的 系数 (coefficient),相应的 称为多项式的 项 (term)。项 中的 称为该项的 次数 (degree)。
所有系数都为零(即零元)的多项式称为 零多项式 (zero polynomial),记作 。对于其它多项式,不妨设 ,即 是系数不为零的项中次数最高的项。此时,自然数 称为多项式的 次数 (degree),而它所在的项 称为 最高次项 (leading term), 也称为 最高次项系数 (leading coefficient)。最高次项系数等于一(即幺元)的多项式称为 首一 (monic)多项式。零多项式的次数不予指定,或者规定为 。
多项式记号中出现的 称为多项式的 不定元 (indeterminate)。它本身没有任何含义,也没有取值范围。它的存在,仅仅是通过它的指数标记系数的位置。所以,多项式也可以写作 上的数列
但是,这样的数列只能出现有限多个不为零的项。如果两个多项式对应的系数数列一样,就称两个多项式相等。这相当于在补齐系数为零的项后,它们的形式和完全一致。下文中,不再区分相等的多项式的形式和的记号:如果必要,读者可以自行补齐系数中空缺的零。
有时候需要将环中的元素代入多项式中的不定元。比如设 是 的多项式且 ,则将 代入多项式 的结果就是 。它的含义是:在多项式的形式和中,将 替换成 ,就能得到 中的算术表达式,而 就是这个表达式在 中运算得到的结果。
「多项式」和「多项式函数」
读者不应混淆这两个概念。多项式只是有限长的系数数列,它并不自动成为函数。尽管这里将环中元素代入不定元的操作确实将多项式映射为多项式函数,但是这样的映射未必是单射。比如, 作为域 上的多项式,显然不等于零多项式;但是 作为多项式函数 ,恒等于零(即费马小定理)。虽然两者概念不同,很多多项式函数的概念都可以推广到多项式的情形,比如可以仿照多项式函数的微分、不定积分、复合等定义多项式的(形式的)导数 、不定积分 、复合 等。这些形式运算并不依赖于任何拓扑结构,但是仍然成立很多运算法则。
对于多项式
多项式的加法运算定义为
而多项式的乘法运算定义为
其中, 项的系数为 。在这样定义的加法和乘法运算下,可以证明, 上的全体多项式构成环,记作 。
多项式 的次数记作 。那些次数为零的多项式是常数多项式,它们以及零多项式相当于 在 中的嵌入。显然, 有零因子当且仅当有 有零因子。
定理
多项式环 是整环,当且仅当 是整环。
整环 上的多项式环 中,加法和乘法的结果满足
这里设 。所以,多项式环中的可逆元也一定是它的常数多项式中的那些可逆元。任何一次及以上的多项式都不是可逆的。
下文的讨论将仅限于整环上的多项式。
约定
下文中,将不加区分地使用「环 上的多项式」和「多项式环 中的多项式」两种说法。比如,多项式在环 上不可约,就是指多项式在环 中不可约。而且,如果 是 的子环,那么 上的多项式将自动成为 上的多项式;对此也不再多加说明。
域上的多项式环
整环上的多项式环中性质最为简单的,当然是域上的多项式环。域 上的多项式环 因为系数可以做除法,所以可以定义带余除法。不妨设非零多项式 的范数 ,而且 。那么,对于 中的多项式 和非零多项式 ,显然可以做带余除法
其中, ,且 或 。这说明,域上的多项式环都是欧几里得整环。
定理
域 上的多项式环 是欧几里得整环,也是主理想整环,也是唯一分解整环。
算法竞赛中,由于计算精度原因,常常考虑的是多项式环 ,此时的模数 要求是质数。这样的环容许辗转相除法等操作。但是,任意模数 对应的多项式环 甚至都不是整环。
成立带余除法意味着多项式的根总对应着它的一个一次因子。
根
多项式 的 根 (root)指的是使得 成立的元素 。
定理
对于域 上的多项式 和域中的元素 ,那么 是 的根,当且仅当 有一次因子 。
证明
带余除法说明存在 ,成立 且 。因而, 是常数多项式或者零多项式,令 ,则必然有 。代入 ,故而有 ,即 。
根的概念可以推广到重根的情形。
重根
如果多项式 有因子 ,且 不能整除 ,则称 是 的 重根 (root of multiplicity )。如果 ,则根 称为 的 重根 (multiple root);如果 ,则根 称为 的 单根 (simple root)。
定理
如果域 上的多项式 有(可能重复的)根 ,那么,它必然有因子 。进而,域 上的多项式 次数为 ,那么它至多有 个根(计重数)。
证明
注意到 是唯一分解整环即可。
虽然域上的多项式成立唯一分解定理,但是并没有一般的办法判断给定的多形式是否可约。次数比较小的情形相对容易。比如说,所有的一次多项式都是不可约多项式。在特殊的域上,所有的不可约多项式都是一次多项式。这样的域称为 代数闭域 。在这样的域上,所有不恒等于非零常数的多项式都有根,因而任何大于一次的多项式都可以进一步分解。一个这样的例子是复数域 。而实数域 上,则存在二次的不可约多项式;有理数域 上,不可约多项式的结构就更为复杂。域论 页面对于有理数域和有限域上的多项式有更多的讨论。
以上结论都是关于域上的多项式。更一般的整环上的多项式,常常可以转化为这样的情形。
下面考虑唯一分解整环 上的多项式环 。直接在 中做运算,因为系数时常不能做除法,很多运算受到限制。不妨考虑将 扩充到它的分式域 ,进而考虑将 中的多项式 在 中做分解。已知 是唯一分解整环,那就可以通过 中 的分解反推出 中的分解。幸而这样的想法总是可行的。
Gauss 引理
对于唯一分解整环 和它的分式域 ,如果 ,那么如果在 中 ,那么必然存在 ,使得 , ,且 。因此,如果 在 中不可约,那么它在 中不可约。
证明
设 在 中可约,且 。设 和 分别为 和 中所有系数的分母的最小公倍数,则有 和 都是 上多项式。令 ,就有 。如果 是 中可逆元,则可以取分解 ,显然满足引理的要求。
否则,如果 中存在不可约元因子 ,这里要证明,等式两侧可以消去这个因子,且保证所有系数仍旧在整环 中。注意到 必然也是素元,因而 是素理想。等式左右两边同时模去 ,则得到 上的多项式 ,这里, 和 是取模后的多项式。因为 是整环, 也是整环,故而可以设 。这说明, 的系数全都可以整除 。因而,等式两侧可以直接消去因子 。
根据唯一分解整环的定义, 至多有有限个这样的不可约元因子,故而有限次消去它们后就转化为了 是 中可逆元的情形。引理就得以证明。
推论
对于唯一分解整环 和它的分式域 ,如果 且 的所有非零系数互素(即最大公因子是 中幺元),则 在 中不可约,当且仅当 在 中不可约。
也就是说,整系数多项式环 中的不可约元都是 中的不可约元。判断整系数多项式是否不可约的一个有效方法是 Eisenstein 判别法。根据 Gauss 引理,它也提供了判断有理系数多项式是否不可约的方法。
Eisenstein 判别法
设 次整系数多项式 ,如果存在质数 满足 对所有 都成立,且 不能整除 , 不能整除 ,则多项式 在有理数域 上不可约。如果 ,则多项式 也在整数环 上不可约。
证明
利用 Gauss 引理可知,如果多项式 在有理数域 上可约,则它也在整数环 上可约。设 是它在 中的分解。将等式的左右两边对质数 取模,则得到 中的分解, 。但是定理的条件说明, ,则必然存在整数 使得 且 ,其中, 。故而,因子 和 的常数项 和 都是 的倍数。故而, 的常数项 必然是 的倍数。这与所给条件相矛盾。
例子
多项式 在 中不可约。对 应用 Eisenstein 判别法即可。
多项式 在 中不可约。否则, 也可约。但是,对 应用 Eisenstein 判别法可知,后者并不可约。
对于唯一分解整环 ,因为相应的分式域 上的多项式环是唯一分解整环,而 Gauss 引理说明,分式域 上的多项式和原来的整环 上的多项式的分解是相互对应的,所以 也是唯一分解整环。因此,有如下定理:
定理
多项式环 是唯一分解整环,当且仅当 是唯一分解整环。
这里的 提供了唯一分解整环不一定是主理想整环的例子。例如,在 中, 并不是主理想。
有很多方法可以将多项式环扩充到更大的集合。比如说,对于整环上的多项式环 ,可以将它扩充到它的分式域,记作 。这个分式域常称作 有理分式域 (field of rational fractions),其中的元素的基本形式为 ,这里, 和 都是多项式。
多元多项式环
多项式环可以推广到含有多个不定元的情形。对于交换幺环 ,可以定义 上的多项式环,即一元多项式环 。进而,可以定义 上的多项式环 ,它可以看作是 上的二元多项式环 。由此,可以归纳地定义 上的 元多项式环 。当 是整环的时候,它上面的任意多元多项式环都是整环;类似地,唯一分解整环的性质也可以传递到任意多元多项式环。
形式幂级数环
也可以考虑形式和中可以有任意多项系数不为零的情形。交换幺环 上的 形式幂级数 (formal power series)定义为
利用与多项式环 一致的方式可以定义幂级数间的加法和乘法运算。并且,此时的形式幂级数也构成环,记作 。这里的形式幂级数并不需要考虑其敛散性,因为实际上每个形式幂级数只是它的系数序列,而并没有赋予更多的拓扑结构。
形式幂级数环的结构很有趣。整环上的多项式环中,可逆元只能是常数。但是,在形式幂级数环中,却可以有
这个现象是普遍的。只要一个形式幂级数的常数项 是 中的可逆元,就一定有 也是可逆的。这是因为如果设
那么,列出系数需要满足的方程组,可以递归地求得 的表达式,其中只涉及到 的逆。
在形式幂级数环上可以定义各种运算,诸如取逆、除法、复合逆、形式导数、初等函数等,详见 多项式技术简介 。
形式洛朗级数环
形式幂级数环还可以进一步拓展,使得它允许负次数的项。交换幺环 上的 形式洛朗级数 (formal laurent series)定义为
这里, 。因此,形式洛朗级数可以有有限多个负次数的项。将之前的加法和乘法拓展到形式洛朗级数上,就能得到形式洛朗级数环,记作 。如果 是域,那么 也是域。
形式洛朗级数环在 Lagrange 反演 中有应用。
中国剩余定理
相关阅读:中国剩余定理
在数论中,中国剩余定理常用来求解数论方程组。对于一般的交换幺环,同样可以建立中国剩余定理。每个同余方程都相当于指定了未知元在某个商环里的像,那么,交换幺环中的中国剩余定理就相当于通过这些商环里的像确定环中的元素。
这个讨论可以转化为形式语言。对于非零交换幺环 和它的理想 ,考虑环同态 ,它将 映射至 。其中, 是陪集,而 表示环的直积:
直积
对于环 和 ,它们的加法群的直积 上可以定义乘法为各个分量分别相乘,则 就成为环,称为环 和 的 直积 (direct prodcut),仍记作 。
同态 的核是 。中国剩余定理要回答的问题就是这样的映射在什么条件下是满射。
在数论的情形下,定理的成立需要这些模数互质。这个条件可以推广到环论的情形。
互素
设环 有理想 和 ,如果 ,则称 和 互素 (comaximal)。
对于幺环的情形,如果考虑主理想 和 ,这个条件就相当于存在 使得 ,这类似于整数互素时的裴蜀定理。利用这个定义,可以完全仿照整数环的情形,建立交换幺环上的 中国剩余定理 (Chinese remainder theorem)。
中国剩余定理
设非零交换幺环 有理想 。如果它们两两互素,那么上述定义的环同态 是满射,它的核等于这些理想的乘积 ,因此,
证明
定理内容很丰富,但仍需证明的结论只有两个,即 是满射和 。关键在于利用好互素的条件。
首先证明 的情形。因为理想 和 互素,即 ,所以, 中幺元 可以写成 的形式,其中, 。因为 且 ,所以 ;同理, 。因而, 起到了类似向量空间中的「基」的作用。故而,对任意像 ,都能找到同态 下的原像 。这说明 是满射。
还需要证明 。对于一般的环总有 ,关键在于其反面。对于任意 ,都有 。故而也成立 。所以,所求得证。
对于 的情形,需要使用数学归纳法。归纳步骤的关键在于证明对于两两互素的理想 总有理想 和 互素。由于 与 都互素,故而对于每个 都存在 和 使得 成立。因而,有 成立。所以, 。这说明,理想 和 互素。
应用:Lagrange 插值公式
相关阅读:Lagrange 插值 、多项式快速插值
插值(interpolation)问题是指,给定一系列点值 ,寻找域 上的多项式 使其满足 对所有 都成立。当然假设所有 互不相同。Lagrange 插值公式给出了这类问题的通解。
对于域 上的多项式 ,条件 等价于 是多项式 的一个根,因而等价于 ,也就是 。所以,插值问题就等价于求解同余方程组
这些一次多项式 两两互质。根据中国剩余定理可知,问题的解应当具有形式
这里, 且 。根据前文推得的等价性可知,这等价于 ,亦即
不妨取 是常数多项式,即
由此,就得到 Lagrange 插值公式
一般地,将这种方法推广,还可以导出 Hermite 插值公式 ,它允许限制多项式在各点处的若干项导数值。
应用:整数同余类的乘法群
相关阅读:原根 、有限生成 Abel 群基本定理
作为中国剩余定理和群论相关内容的一个应用,这里讨论整数模 乘法群的结构。本节略去同余类的横线记号。
整数模 乘法群 (multiplicative group of integers modulo )指的是 ,即商环 中的可逆元的乘法群(也称单位群)。群 的阶是 ,因为存在逆元的充要条件就是与 互质。这里的 是 欧拉函数 。而且,群 总是 Abel 群。
根据算术基本定理,模数 可以分解为不同的质数的幂的乘积:
容易验证,对于整数环的理想,理想互素的条件等价于理想的生成元互素。所以,应用中国剩余定理可以得到
环的同构意味着相应的乘法结构也同构,所以
这说明 ,即欧拉函数是积性函数。
因此,要研究一般的模数的情形,只要考虑素数幂 作为模数的情形就可以了。对于素数幂的情形,需要分别考虑 和 为奇素数的两种情形:
一般的模数的情形的乘法群的结构也随之确定。从现有的结果能够知道整数模 乘法群是循环群有且只有模数 取
时,其中, 是奇素数;否则,整数模 乘法群一定有子群 ,不可能是循环群。当乘法群是循环群的时候,乘法群的生成元就称为该模的 原根 (primitive root)。因此,这里的定理给出的正是原根存在的充要条件。
当然,对乘法群结构的分析蕴含着比原根存在的条件更多的信息。它清楚地反映了乘法群中不同元素的阶。群 中,满足 的元素 ,也就是同余方程 的解,它称为 模 的 次单位根 ( -th root of unity modulo );阶恰为 的元素,则称为 模 的 次本原单位根 (primitive -th root of unity modulo )。利用乘法群的结构,这些单位根的存在性和数目都可以得到精确的计算。最后,群 中所有元素的阶的最小公倍数,即对所有 都满足 的最小正整数 ,表示为 的函数,就是 Carmichael 函数 。它的一系列性质,都可以从乘法群的结构中获得。
参考资料和注释
本页面最近更新:2024/11/28 02:32:02 ,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:c-forrest , Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用