信息安全数学基础第05章

第5章有限域的概念第5章有限域的概念群环整环中的因子分解由整环构造域第5章有限域的概念通过前面的学习，我们已经知道对于给定的两个整数a和b，利用带余数除法一定会找到一个整数q以及一个非负整数r，使得a=qb+r，在后面的学习过程中，还会发现，这个规则对于多项式，高斯整数等也是成立的。于是，人们为了将这样一大类的研究对象进行统一处理，引入了一个新的概念－欧氏环。如此，就可以在欧氏环中做我们所熟知的除法，因子分解等等，许多的结论我们不必再分别对整数，多项式，高斯整数等一一验证，只要知道是欧氏环，那么相应的结论就是正确的。第5章有限域的概念类似这样的一套由具体到抽象的理论是由一些伟大的数学家迦罗瓦，阿贝尔等将我们所熟知的数上的一些理论加以高度概括，提炼出来的结果－称之为近世代数又称之为抽象代数。和我们已经接触到的经典代数中的初等代数、高等代数和线性代数不同，其研究对象不再是代数方程和线性方程组，而是代数系统。第5章有限域的概念定义：设S是任意一个集合，并记S×S×…×S为所有有序对(s1,s2,…,sn)，si

S，1≤i≤n，所构成的集合，则称由S×S×…×S到S的映射为集合S上的（n元）代数运算，并称由集合S以及定义在集合S上的一个或多个代数运算构成的系统为代数系统或代数结构。注：在这个定义中，要求有序对(s1,s2,…,sn)

S×S×…×S的像必须在集合S中，即运算要满足封闭性。第5章有限域的概念例如，由整数集合Z以及定义在其上的整数加法运算“+”所构成的系统就是一个代数系统；而由整数集合Z和整数加法运算“+”以及乘法运算“×”所构成的系统也是一个代数系统。第5章有限域的概念本章为了引出有限域的概念，将首先介绍两个代数系统：群和环，包括它们的定义及相关性质，最后给出有限域的定义及其构造方法。5.1群群的概念子群、陪集与拉格朗日定理5.1群群的概念定义5.1.1：设G是定义了二元运算“◦”的非空集合，如果在集合G中：1）

a,b,c

G，有(a◦b)◦c=a◦(b◦c)2）存在一个特殊的元素e，使得

a

G，有e◦a=a◦e=a

3）

a

G，可以找到一个特殊的元素a-1

G，使得a◦a-1=a-1◦a=e则称{G,◦}为群，并称元素e为群{G,◦}的单位元，称a-1为元素a的逆元。

注：群的条件：结合律、单位元（幺元）、逆元5.1群群的概念若群{G,◦}中的运算“◦”为大家已知，则可将群{G,◦}简记为G。同时由于群{G,◦}中的运算满足结合律，故可以在群{G,◦}中用记号a1◦a2◦…◦an表示n个元素a1,a2,…,an做运算的结果。5.1群群的概念定义5.1.2：若对群{G,◦}中任意的元素a，b，有a◦b=b◦a即运算“◦”满足交换律，则称该群为阿贝尔（或可换）群。

5.1群群的概念例5.1.1：证明(Z,+)构成阿贝尔群，(Z,×)不构成群。证明：由整数加法的运算性质知加法运算满足封闭性(即任意两个整数做加法还是整数)，结合律与交换律，同时容易验证：1）整数0是整数集合在加法运算下的单位元；2）对任意的整数a，都可以找到其对应地逆元-a。因而(Z,+)构成阿贝尔群。虽然容易验证整数集合在乘法运算下有单位元1，但是对任意的整数a≠1都找不到其对应的逆元。因而(Z,×)不构成群。

5.1群群的概念按照经典代数中的习惯，通常我们把群{G,◦}中的运算“◦”称为乘法或加法，记为“×”或“+”，并相应地把群G称为乘法群或加法群。特别地，在加法群中，用-a表示a的逆元，称其为a的负元；而以0表示加法的单位元，称其为加法群的零元。注：这里所说的乘法群中的乘法或加法群中的加法并不一定都是数的相乘或者相加，更多的则是表示“抽象加法”或“抽象乘法”的含义。5.1群群的概念例5.1.2：给定由模4的全体剩余类构成的集合Z4={[0],[1],[2],[3]}，则可对Z4定义加法“+”运算：[i]+[j]=[i+j]。该“+”运算可用如下运算表来完全刻划在如上定义的“+”运算下，{Z4,+}构成群。+[0][1][2][3][0][0][1][2][3][1][1][2][3][0][2][2][3][0][1][3][3][0][1][2]5.1群群的概念事实上，由上述运算表易知1）Z4对该加法“+”运算封闭；“+”满足结合律；2）由于对任意的元素[a]Z4，都有[0]+[a]=[0+a]=[a+0]=[a]+[0]=[a]因而[0]为Z4中的加法零元；5.1群群的概念3）而对Z4中任意的元素[a]，都可以找到Z4中的元素­[-a]，使得[-a]+[a]=[-a+a]=[0]=[a+(-a)]=[a]+[-a]因而Z4中的每个元素都有负元，具体地[0]的负元是自身，[1]的负元为[-1]=[3][2]的负元是[-2]=[2]，[3]的负元为[-3]=[1]因而{Z4,+}构成了加法群，称之为整数模4的剩余类加群。利用同样的证明过程，可以得到整数模n的剩余类加群{Zn,+}。

5.1群群的概念一般地，在乘法群中，一个元素a

G作n次运算的结果可以记为an=aa∙∙∙a同时称an为a的n次幂；而在加法群中，一个元素a

G作n次运算的结果则可以记为na=a+a+∙∙∙+a5.1群群的概念并且类似于普通的数的集合中的加法和乘法运算，群中的加法和乘法运算具有如下性质对于乘法：a-n=(a-1)n，anam=an+m，(am)n=anm对于加法：(-n)a=n(-a)，na+ma=(n+m)a，m(na)=(mn)a在n=0时，作如下约定：在乘法记号中a0=e；在加法记号中0a=0，其中最后一个“0”为加法群中的零元。

5.1群群的概念定义5.1.3：设a为群G中的元素，则称使得an=e的最小正整数n为元素a的阶，记为|a|，如果这样的n不存在，则称a的阶为无限（或称是零）。由定义5.1.3可知，群中单位元的阶是l，而其他任何元素的阶都大于1，例如在非零有理数乘法群中，单位元1的阶是1，而元素-1的阶是2，其余元素的阶均为无限。5.1群群的概念定义5.1.4：群G中的元素个数称为G的阶，通常记为|G|。5.1群群的概念例5.1.3：集合G={1,-1,i,-i}关于数的普通乘法作成群，即4次单位根群。其中群G的阶为4，元素l的阶是l，-1的阶是2，而虚单位根i与-i的阶都是4。5.1群群的概念定义5.1.5：设S为定义了代数运算“◦”的任一非空集合。若在集合S中，运算“◦”满足封闭性与结合律，则称{S,◦}为半群。5.1群群的概念例5.1.4：设A={1,2,3,4}，而令S为A的全部子集构成的集合（通常称之为A的幂集），则易知{S,∩}及{S,∪}都是半群。

5.1群子群、陪集与拉格朗日定理给定群G，我们可以从群G中找到一些特殊的子集，使其对于群G中所定义的运算也能够构成群。5.1群子群、陪集与拉格朗日定理定义5.1.6：如果群G的子集H对于群G的运算也构成了群，则称H为群G的子群，并称群G的除了{e}和G之外的子群为G的真子群。例如容易验证所有偶数构成的集合就是整数加法群的真子群。5.1群子群、陪集与拉格朗日定理定义5.1.7：如果群G中存在一个子集H，使得子集H中的任意元素b，都可以表示为H中某个特殊的元素a的幂次，则称子集H为群G的循环子群，而称元素a为H的生成元，记为H=(a)。特别地，若H=G，则称群G为循环群。注：对于乘法群来说，元素a的幂次表示为am；对于加法群来说，元素a的幂次表示为na。5.1群子群、陪集与拉格朗日定理例5.1.5：容易验证整数模4的剩余类加群Z4中的任意元素都可以由元素[1]做若干次运算而得到，即[1]是Z4的生成元。

显然循环群的乘法满足交换律，故循环群都是可换群。同时一个循环群的生成元很可能不止一个。例如容易证明[3]也是整数模4的剩余类加群Z4的生成元。5.1群子群、陪集与拉格朗日定理推论5.1.1：由群G中一个固定的元素a的所有幂次所构成的子群，称为由a生成的子群，记为(a)。注：子群(a)必然是循环群，并且若这个子群的阶是有限的，则此子群的阶就是元素a的阶，而若子群的阶是无限的，则元素a的阶也是无限的。

5.1群子群、陪集与拉格朗日定理半群群阿贝尔群循环群封闭性√√√√结合律√√√√单位元√√√逆元√√√交换律√√生成元√5.1群子群、陪集与拉格朗日定理定义（子群）（补充）：群G的子集H称为子群，若1）1

H；2）若x,y

H，则xy

H，即H在运算下封闭；3）x

H，则x-1

H。5.1群子群、陪集与拉格朗日定理定理（补充）：群G的子集H是一个子群当且仅当H非空，且对任意x,y

H有xy-1

H。5.1群子群、陪集与拉格朗日定理定理（补充）：群G的任意一簇子群的交集还是G的子群。5.1群子群、陪集与拉格朗日定理定义5.1.8（集合的积）：设X和Y是群G的两个非空子集，于是子集X与Y

的积记为XY={xy|x

X,y

Y}特别地，如果Y={y}是一个单元素集，而子集X={x1,x2,…}，那么子集X和Y的积为XY={x1y,x2y,…}此时我们记XY为Xy，并称Xy为元素y右乘X的积。5.1群子群、陪集与拉格朗日定理定义5.1.9：设H为群G的子群，a

G，则称群G的子集aH={ax|x

H}为群G关于子群H的一个左陪集，而称Ha={xa|x

H}为群G关于子群H的一个右陪集。同时称a为代表元。5.1群子群、陪集与拉格朗日定理定理5.1.1：设H为群G的子群，则a，b

G，Ha=Hb与下面两个条件等价1）a

Hb

2）ab-1

H5.1群子群、陪集与拉格朗日定理证明：（证明思路）本题要证明如下结论：Ha=Hb↔a

Hb↔ab-1

H因此，我们分成三步来证明：1）a

Hb↔ab-1

H2）Ha=Hb↔a

Hb2.1）a

Hb→Ha=Hb2.2）

Ha=Hb→a

Hb，即：Ha=Hb→ab-1

H5.1群子群、陪集与拉格朗日定理1）证明ab-1∈H↔a

Hb：设ab-1

H，则存在h

H，使得ab-1=h于是a=hb

Hb即a

Hb由于以上每步的推导都是可逆的，因此ab-1∈H↔a

Hb5.1群子群、陪集与拉格朗日定理2.1）证明a

Hb→Ha=Hb：设a

Hb，则存在h∈H使得a=hb因而h-1a=h-1hb=b即b=h-1a

首先x

Ha，存在h1

H使得x=h1a=h1(hb)=(h1h)b5.1群子群、陪集与拉格朗日定理由子群H对乘法运算的封闭性得到h1h

H，因而x=(h1h)b

Hb故Ha

Hb其次

y

Hb，存在h2

H使得y=h2b=h2(h-1a)=(h2h-1)a由子群H对乘法运算的封闭性得到h2h-1

H5.1群子群、陪集与拉格朗日定理因而y=(h2h-1)a

Ha故Hb

Ha综上，得到Ha=Hb5.1群子群、陪集与拉格朗日定理2.2）证明Ha=Hb→ab-1

H：设Ha=Hb，则ha

Ha，都存在h’

H，使得ha=h’b即ab-1=h-1h’

H进而ab-1

H综上，结论成立。5.1群子群、陪集与拉格朗日定理定理（补充）：设H为群G的子群，则a，b

G，aH=bH与下面两个条件等价1）a

bH

2）b-1a

H5.1群子群、陪集与拉格朗日定理定理5.1.2：设H为群G的子群，a，b

G，则1）a

Ha2）右陪集Ha与Hb或者相等或者相交为空集，即Ha=Hb或Ha∩Hb=Φ5.1群子群、陪集与拉格朗日定理证明：1）因为H为群G的子群，所以H中有单位元e，使得a

G，有a=ea

Ha5.1群子群、陪集与拉格朗日定理2）若Ha∩Hb≠Φ，则存在x

Ha∩Hb由x

Ha，可以得到Hx=Ha而由x

Hb，又可以得到Hx=Hb所以Ha=Hb5.1群子群、陪集与拉格朗日定理3）因为每个右陪集Ha都是G的子集，所以这些右陪集的并也是G的子集，即另一方面，g

G，由1)知g

Hg，而显然有所以5.1群子群、陪集与拉格朗日定理由g的任意性得到所以5.1群子群、陪集与拉格朗日定理由定理5.1.2我们看到：1）每个右陪集的代表元都含在该右陪集内；2）任两个右陪集要么相等，要么不相交；3）将不重复的全部右陪集并起来恰好等于整个群G，即群G的所有不重复的右陪集构成了G的一个划分。5.1群子群、陪集与拉格朗日定理定义5.1.10：设H为群G的子群，由上述定理决定的G的划分称为G的一个右陪集分解。5.1群子群、陪集与拉格朗日定理特别地，由上可见群G的右陪集分解具有如下特点：1）分解式中必含有子群H（即以单位元为代表的右陪集），而其余的右陪集都不是G的子群；备注：因为当a

H时，因为a

He，因此Ha=H；当时，Ha不封闭。否则，存在h,g

H，ha=g，即即Ha不封闭，与H为子群矛盾。故此时Ha不是子群。5.1群子群、陪集与拉格朗日定理2）右陪集分解式中出现的右陪集彼此都不相交；3）分解式中每个右陪集的代表元都可以适当替换。5.1群子群、陪集与拉格朗日定理设H为群G的子群，若记SR={Ha|a

G},SR为H的所有不重复的右陪集组成的集合，SL={cH|c

G}，SL为H的全部不重复的左陪集组成的集合。则左陪集将与右陪集具有完全相似的性质。同时有如下结论5.1群子群、陪集与拉格朗日定理定理5.1.3：设H为群G的子群，则SR与SL之间存在双射。证明：（证明思路）按照如下步骤证明：1）构造一个关系φ2）证明φ是映射：x1=x2→

φ(x1)=φ(x2)3）证明φ是满射：原象都存在4）证明φ是单射：x1≠x2→φ(x1)≠φ(x2)的逆否命题：

φ(x1)=φ(x2)→x1=x25）得到φ是双射5.1群子群、陪集与拉格朗日定理1）关系的构造：作φ:SR→SL其中φ(Ha)=a-1H5.1群子群、陪集与拉格朗日定理2）证明φ必是映射：

Ha，Hb

SR，若Ha=Hb则ab-1

H即存在h

H，使得

ab-1=h即

b-1=a-1h进而b-1

a-1H故a-1H=b-1H即φ(Ha)=φ(Hb)这说明φ是个映射。5.1群子群、陪集与拉格朗日定理3）证明φ必是满射：

cH

SL，存在Hc-1

SR使

φ(Hc-1)=(c-1)-1H=cH所以φ必是满射。5.1群子群、陪集与拉格朗日定理4）证明φ必是单射：设

φ(Ha)=a-1H若a-1H=b-1H，则ab-1H=H即存在h1，h2

H，使得ab-1h1=h2，即ab-1=h2h1-1进而a=h2h1-1b即

h2-1a=h1-1b，故Ha=Hb所以φ必是单射。5.1群子群、陪集与拉格朗日定理5）综上知φ必是双射。综上，命题得证。5.1群子群、陪集与拉格朗日定理由定理5.1.3我们知道集合SR与SL中的元素个数相同。5.1群子群、陪集与拉格朗日定理定义5.1.11：若H为群G的子群，则称H的右（左）陪集的个数为H在G中的指数，记为[G:H]。5.1群子群、陪集与拉格朗日定理引理5.1.1：设H为群G的子群，则H与H的任一个右陪集Ha之间都存在双射。证明：设φ:H→Ha，其中h

H，有φ(h)=ha1）h

H，作为h在φ下的象ha是唯一确定的，所以φ是映射。2）ha

Ha，显然ha有原象h，所以φ是满射。5.1群子群、陪集与拉格朗日定理3）设φ(h1)=h1a，φ(h2)=h2a若

h1a=h2a则h1aa-1=h2aa-1即h1=h2所以φ必是单射。综上知φ是双射。

5.1群子群、陪集与拉格朗日定理由引理5.1.1可知，子群的互不相等的右陪集不相交且彼此都含有相同数目的元素。5.1群子群、陪集与拉格朗日定理定理5.1.4（拉格朗日定理）：设H为群G的子群，若|G|=N，|H|=n且[G:H]=j则N=nj5.1群子群、陪集与拉格朗日定理证明：因为[G:H]=j，即H在群G中的右陪集只有j个，从而有G的右陪集分解：G=Ha1∪Ha2∪Ha3∪…∪Haj其中Ha1=H由引理5.1.1知，|Ha1|=|Ha2|=|Ha3|=…=|Haj|=n所以|G|=|Ha1|j即N=nj5.1群子群、陪集与拉格朗日定理由等式N=nj知子群H的阶n是G的阶N的因子，于是有如下推论：5.1群子群、陪集与拉格朗日定理推论5.1.2：设G为有限群，则a∈G，其阶m必是|G|的因子，即|a|||G|。证明：设以元素a生成G的一个循环子群H=(a)，则由拉格朗日定理知|H|||G|但|H|=m，所以m||G|即|a|||G|

5.2环在基础代数中我们所及的数的集合，例如整数集、实数集与有理数集，都定义了两种不同的二元运算：加法和乘法。在这一节中我们定义一个与这些数的代数系统具有相似运算性质的代数结构：环。5.2环环的定义多项式环5.2环环的定义定义5.2.1：设在非空集合R中定义了两个二元运算“+”与“·”，如果在集合R中1）{R,+}构成阿贝尔群；2）{R,·}构成半群；3）乘法“·”对加法“+”满足左、右分配律，即a,b,c

R，有a·(b+c)=a·b+a·c且(b+c)·a=b·a+c·a则称{R,+,·}为环。5.2环环的定义例5.2.1：在环{R,+,·}中，取集合R为整数集Z，“+”和“·”为整数的加法和乘法运算，则容易验证{R,+,·}构成环，称之为整数环，记为Z。同理还可以得到有理数环，实数环，复数环，由于这四个环都是由数的集合组成的，故均称之为数环。5.2环环的定义例5.2.2：设集合Z[i]={a+bi|a,b

Z}则按照整数加法运算，集合Z[i]也构成了环，称为高斯整数环。注：高斯整数是指实数和虚数部分都是整数的复数。5.2环环的定义例5.2.3：模m的剩余类环{Zm,+,·}，前边我们曾讨论了模m的剩余类加群{Zm,+}，这里再为Zm定义一个乘法“·”：[i]·[j]=[i·j]于是可以验证{Zm,+,·}构成一个环。为了便于理解，这里特取m=7，接下来证明{Z7,+,·}构成环。5.2环环的定义证明{Z7,+,·}构成环。事实上：1）{Z7,+}正是模7剩余类加群；2）{Z7,·}是半群：由下边的乘法运算表可知{Z7,·}对乘法运算封闭，且满足结合律；·[0][1][2][3][4][5][6][0][0][0][0][0][0][0][0][1][0][1][2][3][4][5][6][2][0][2][4][6][1][3]5][3][0][3][6][2][5][1]4][4][0][4][1][5][2][6][3][5][0][5][3][1][6][4][2][6][0][6][5][4][3][2][1]5.2环环的定义3）a,b,c

Z7，有[a]·([b]+[c])=[a]·[b+c]

=[a·(b+c)]

=[a·b+a·c]

=[a·b]+[a·c]

=[a]·[b]+[a]·[c]同理([b]+[c])·[a]=[b]·[a]+[c]·[a]因而{Z7,+,·}构成环。5.2环环的定义环{R,+,·}在集合R上定义了两个二元运算，并且这两个二元运算通过分配律建立了彼此的联系，但同时注意到集合R对于乘法只要求构成半群（即乘法满足封闭性和结合律），所以为环在乘法方面留下了很大的发展空间，一旦某些乘法再满足其它一些条件，就可以得到一些特殊类型的环。首先引入如下定义：5.2环环的定义定义5.2.2：若环R中存在非零元素a和b，使得a·b=0则称a是R的一个左零因子，b是R的一个右零因子，进一步地，若环R中的元素a既是左零因子，又是右零因子，则称a为零因子。注：此处等式右边的0指的是加法的零元。5.2环环的定义例5.2.4：容易验证在环{Z6,+,·}中，有[2]·[3]=[0]因而[2]是Z6的一个左零因子，同时[3]是Z6的一个右零因子，又由[3]·[2]=[0]知[2]也是Z6的一个右零因子，[3]也是Z6的一个左零因子，而因而[2]和[3]都是Z6的零因子。但是观察例5.2.3中环{Z7,+,·}的乘法运算表，我们会发现找不到这样的非零元素a与b，故环{Z7,+,·}中既无左零因子，也无右零因子。5.2环环的定义注：在环R中1）左零因子和右零因子这两个概念彼此依赖，有左零因子有右零因子；2）若a是R的左零因子，一般a未必同时是R的右零因子；3）若环R是交换环（见定义5.2.4），则R的每个左（或右）零因子都是零因子。5.2环环的定义定义5.2.3：若环R中没有左零因子（自然也就没有右零因子），则称环R为无零因子环。进一步地给出如下定义：5.2环环的定义定义5.2.4：1）若环{R,+,·}中具有乘法运算的单位元，则称环{R,+,·}为有单位元环。2）若环{R,+,·}中的乘法运算满足交换律，则称环R为可换环/交换环（交换环需不需要含单位元目前有争议）。3）一个不含零因子的交换环称为整环。4）若环{R,+,·}中的非零元在乘法运算下构成群，则称环{R,+,·}为除环。5）可交换的除环称为域。5.2环环的定义定义（整环）（补充）：交换环R称为整环（IntegralDomain），若1≠0，且乘法消去律成立：当ca=cb，c≠0时，a=b。注：1）此定义说明整环需要含有单位元（目前有争议）；2）假设乘法单位元1不等于加法单位元0是用以除去平凡的环{0}。整环是整数环的抽象化，它很好地继承了整数环的整除性质，使我们能够更好地研究整除理论。5.2环环的定义定理（补充）：每个域都是整环。证明：假设ab=ac，其中a≠0。两边乘以a-1得到a-1ab=a-1ac所以b=c得证。5.2环环的定义注意：1）环中的乘法单位元显然不只代表整数1，例如{Z7,+,·}中的单位元为[1]。2）并不是每个环都有单位元，例如偶数环。3）若环R中有单位元,则这个单位元必是唯一的。5.2环环的定义例5.2.5：所有数环以及剩余类环Zm都是可换环。整数环，模m剩余类环(m为素数时)都是整环；模m剩余类环(m为合数时，有零因子)不是整环。5.2环环的定义接下来，有必要对域的概念及性质做进一步地强调。首先，域是定义了两个二元运算：加法和乘法的非空集合。1）该集合对加法构成了阿贝尔群，其加法的零元记为0；2）集合中的所有非零元对乘法也构成了阿贝尔群，其乘法的单位元记为e，且0≠e。3）两个二元运算乘法和加法通过分配律a(b+c)=ab+ac联系在一起。前面曾介绍的很多数环都是域(称为数域)，例如有理数域Q，实数域R，复数域C。5.2环环的定义定义5.2.5：只包含有限个元素的域称为有限域，或迦罗瓦（Galois）域。

5.2环环的定义环无零因子环整环有单位元环除环可换环/交换环域有限域非零元有乘法逆元乘法有单位元非零元在乘法在构成群乘法可交换5.2环环的定义补充：目前关于可换环和整环的定义有歧义。半群群Abel群环无零因子环可换环含幺环整环除环域5.2环环的定义定理5.2.1：若p是素数，则模p的剩余类环Zp构成域。证明：首先模p的剩余类环Zp是不含零因子的可换环，即整环。否则设[a]是Zp的任意一个零因子，则存在[b]Zp，且[b]≠[0]使得[a][b]=[0]由[b]≠[0]，得到p∤b5.2环环的定义而由[a][b]=[ab]=[0]又知p|ab故p|a即[a]=[0]，也即Zp的零因子只有[0]，故Zp是整环。其次易知Zp有单位元[1]。5.2环环的定义最后由域的定义只需证明每个非零元素[a]都有逆元即可。为此，

[x]Zp，作映射f:[x]→[a][x]则由乘法运算的封闭性知[a][x]Zp，即f(Zp)Zp若f(Zp)=Zp则必定可以找到一个[x]Zp，使得[a][x]=[1]，即[x]=[a]-15.2环环的定义下面证明f(Zp)=Zp由于f(Zp)={[a][x]|[x]Zp}故当[x]取遍Zp时，[a][x]取遍Zp；且若[x1]≠[x2]，则由剩余类环Zp无零因子知[a][x1]≠[a][x2]因而|

f(Zp)|=|Zp|即集合f(Zp)与Zp有相同个数的元素，因而结合f(Zp)Zp，就得到f(Zp)=Zp5.2环环的定义定义5.2.6（子环）：若环R的一个子集S在环R的加法和乘法运算下也构成环，则称S为R的子环。类似地可以给出如下子整环，子除环和子域的定义。5.2环环的定义定义5.2.7：若整环（除环或域）R的子集S在整环（除环或子域）R的加法和乘法运算下也构成整环（除环或域），则称S为整环（除环或域）R的子整环（子除环或子域）。5.2环环的定义例5.2.6：容易验证整数模6的剩余类环Z6中的子集S={[0],[2],[4]}构成了Z6的子环，且该子环还是一个域，其中[4]为单位元，而[2]与[2]互为逆元。

5.2环环的定义定义5.2.8（理想）：设I是环R的一个子环，若a

I，r

R，都有ra

I（或ar

I），则称I是R的一个左理想（或右理想）；若a

I，r

R，都有ar

I且ra

I，则称I是R的一个理想（理想子环的简称）。注：由理想的定义可知，理想的乘法具有“吸收性”。5.2环环的定义例5.2.7：任一个环R至少都有如下两个理想：{0}—零理想，R—单位理想，统称为环R的平凡理想，而将其它理想（若存在）称之为环R的真理想。5.2环环的定义例5.2.8：容易验证偶数环是整数环的理想。

5.2环多项式环在基础代数中，我们将多项式f(x)表示为a0+a1x+…+anxn其中系数ai的通常为实数或复数；并将x看成是变元，即可以把x替换成任意的数α，进而得到数a0+a1α+…+anαn本小节我们将把所熟悉的多项式的概念和运算作以下简单推广。5.2环多项式环设R是任意环，则环R上的多项式可以表示为f(x)=a0+a1x+…+anxn其中n为非负整数，系数ai为环R上的元素，x是不属于环R的一个符号，称为环R上的不定元（或称未定元）。约定当系数ai=0时，项aixi可以不写，在此约定下，上面的多项式也可以等价地表述为f(x)=a0+a1x+…+anxn+0xn+1+…+0xn+h其中h为任意正整数。5.2环多项式环这样，对环R上的两个多项式f(x)=a0+a1x+…+anxng(x)=b0+b1x+…+bmxm进行比较时，就可以假设他们都具有相同的幂指数。环R上的两个多项式相等的充要条件可以表示为：f(x)=g(x)ai=bi，0≤i≤n5.2环多项式环两个多项式f(x)与g(x)的加法与乘法运算分别定义为f(x)+g(x)=(a0+b0)+(a1+b1)x+…+(an+bn)xn

f(x)g(x)=c0+c1x+…+cn+mxn+m其中，5.2环多项式环容易验证环R上的多项式集在定义了如上的多项式的和与乘积运算之后构成环。称之为环R上的多项式环，记为R[x]。R[x]中的零元是系数全为零的多项式，这个多项式称为零多项式，记为0。5.2环多项式环定义5.2.9：设f(x)=a0+a1x+…+anxn为环R上的一个非零多项式，故可设an≠0，并称an为多项式f(x)的首系数，a0为f(x)的常数项，而n称为f(x)的次数，记n=deg(f(x))=deg(f)并约定deg(0)=-∞次数≤0的多项式称为常数多项式。若环R有单位元1且f(x)的首系数为1，就称f(x)为首一多项式。5.2环多项式环多项式的分类和性质：类型子类型形式次数常数多项式零多项式f(x)=0-∞零次多项式f(x)=a00非常数多项式不可约多项式f(x)=a0+a1x+…≥1可约多项式f(x)=a0+a1x+…≥15.2环多项式环例5.2.9：多项式环Z7[x]中，多项式f(x)=6x5+5x4+x2+4的次数deg(f(x))=5首系数为6，常数项为4。由于多项式f(x)的首系数不为1，因而f(x)不是首一多项式。5.2环多项式环定理5.2.2：设f(x)和g(x)R[x]，则deg(f(x)+g(x))≤max(deg(f(x)),deg(g(x)))deg(f(x)·g(x))≤deg(f(x))+deg(g(x))若R是整环，则

deg(f(x)·g(x))=deg(f(x))+deg(g(x))5.2环多项式环例5.2.10：多项式环Z6[x]中，多项式f(x)=2x3+x2+4，g(x)=3x2+x+3则deg(f(x))=3，deg(g(x))=2而f(x)+g(x)=2x3+4x2+x+1f(x)g(x)=5x4+x3+3x2+4xdeg(f(x)+g(x))=3=max(deg(f(x)),deg(g(x)))deg(f(x)·g(x))=4<deg(f(x))+deg(g(x))=55.2环多项式环而在多项式环Z7[x]中，多项式f(x)=6x5+5x4+x2+4，g(x)=3x4+5x2+x+5则deg(f(x))=5，deg(g(x))=4而f(x)+g(x)=6x5+x4+6x2+2f(x)g(x)=4x9+x8+2x7+6x6+x3+4x2+6deg(f(x)+g(x))=5=max(deg(f(x)),deg(g(x)))deg(f(x)·g(x))=9=deg(f(x))+deg(g(x))5.2环多项式环若我们将环R中的元素看成是常数多项式，则R可以看成是R[x]的一个子环，且容易证明R[x]将具有与环R完全相似的性质，即5.2环多项式环定理5.2.3：设R是一个环，则R[x]是可换环当且仅当R是可换环；R[x]是有单位元的环当且仅当R有单位元；R[x]是整环当且仅当R是整环。5.2环多项式环并且与整数环上的素数相对应，在域F上的多项式环F[x]上可以定义既约多项式（或称为不可约多项式）。5.2环多项式环定义5.2.10（不可约多项式）：设f(x)是次数大于零的多项式，若除了常数和常数与多项式f(x)本身的乘积以外，f(x)再不能被域F上的其它多项式除尽，则称f(x)为域F上的既约多项式或不可约多项式。5.2环多项式环定义（不可约多项式）（补充）：设F是域，则非常数多项式f(x)F[x]在F[x]中是不可约的当且仅当在F[x]中没有如下的因子分解：f(x)=g(x)h(x)其中deg(g),deg(h)<deg(f)。注：以上定理说明deg(g),deg(h)>0，即g(x)和h(x)不能为常数多项式，否则条件deg(g),deg(h)<deg(f)得不到满足。5.2环多项式环注：由此定义我们可以看出：1）f(x)是不可约多项式的充要条件为f(x)不能再分解为两个次数比f(x)的次数更低的多项式的乘积。2）f(x)是否可约与所讨论的域有很大关系。例如f(x)=x2+1在实数域上是不可约的，但在复数域上可分解为f(x)=(x+i)(x-i)但不论在哪一个域上，凡是一次首一多项式都是不可约多项式。5.2环多项式环与数论部分中整数的带余除法以及唯一分解定理类似，下面我们不加证明地给出域F的多项式环F[x]中的带余除法以及唯一分解定理。5.2环多项式环定理5.2.4：设f(x)和g(x)F[x]，g(x)≠0，则存在多项式q(x)和r(x)F[x]，使得f(x)=q(x)g(x)+r(x)其中deg(r(x))<deg(g(x))注：在整环和域中，这种分解形式是唯一的。5.2环多项式环定理5.2.5：域F的多项式环F[x]中的每一个首一多项式必定可以分解为首一不可约多项式的乘积，并且当不考虑因式的顺序时，这种分解是唯一的。5.3整环中的因子分解在数论中我们讨论了整数环的唯一分解定理，在前一节中我们又看到这样这个定理对于多项式也是成立的，而他们的共性在于它们都是有单位元的整环，为此本节我们讨论有单位元的整环中元素的分解问题。5.3整环中的因子分解一些基本概念唯一分解整环5.3整环中的因子分解一些基本概念在本节我们把整数环中的整除、因子以及素数等进行推广。5.3整环中的因子分解一些基本概念定义5.3.1：设D是有单位元的整环，则a,b

D，1）若c=ab，则称a是c的因子，并称a可整除c，记作a|c。2）若a|b且b|a，则称a与b相伴，记作a~b。3）若a与b之积ab为单位元，则称a与b互为逆元，此时也称a与b皆为可逆元（或称a与b为单位）。4）若c=ab，且a与b都不是可逆元，则称a是c的真因子。5.3整环中的因子分解一些基本概念例5.3.1：整数环中两个整数相伴的充要条件为：这两个整数相等或只差一个负号；在多项式环中两个多项式相伴的充要条件为：这两个多项式相差一个常数多项式；高斯整数环Z[i]中的可逆元为1，i，故两个高斯整数相伴的充要条件为：这两个高斯整数相差1或i，例如-3+i~1+3i。思考：大家能总结相伴所需的一般性条件吗？5.3整环中的因子分解一些基本概念由定义5.3.1可得以下基本事实，其中集合U(D)表示整环D中的所有可逆元构成的集合（因其是乘法群，故也称作单位群）：1）由于

a

D，均有0=a·0，a=a·1，因而任意元素都是0的因子，而单位元l是任意元素的因子。2）由于若u

U(D)，则a

D，均有a=u(u-1a)，因而可逆元是任意元素的因子。5.3整环中的因子分解一些基本概念3）由于a,b,c

D，若a|b且b|c，则a|c，因而整除关系满足传递性。4）两元素相伴，则它们相差一个可逆元因子：设a~b，则a|b且b|a，即存在元素u和v使得b=ua，a=vb因而b=uvb，由于D中有单位元且无零因子，因而由b(1-uv)=0，即得uv=1，所以u和v都是可逆元。5）相伴关系是等价关系。5.3整环中的因子分解一些基本概念6）可逆元无真因子，且所有可逆元都与单位元l相伴：若u

U(D)，u=ab，则u-1u=u-1ab=a(u-1b)=(u-1a)b=1即a与b都是可逆元，因而可逆元无真因子；又

u

U(D)，有u-1u=1，而u-1为可逆元，故由4）知u与1相伴。5.3整环中的因子分解一些基本概念定义5.3.2：设D是有单位元的整环，且D*为D中的所有非零元构成的集合，则a,b

D，p

D*\U(D)，若由等式p=ab，可知a

U(D)，或b

U(D)，则称p是不可约元或既约元；若由p|ab，可知p|a或p|b，则称p是素元。注：1）“\”表示集合的减法运算；2）由以上定义可知，既约元或者素元一定不是可逆元；3）既约元没有真因子。5.3整环中的因子分解一些基本概念例5.3.2：在多项式环中的既约元与素元均指不可约多项式；在整数环中，既约元与素元均是指全体素数；但在高斯整数环中，素数就不一定是既约元了。例如，2是素数，且2=(1+i)·(1-i)，而高斯整数环中的可逆元只有1与i，故1+i与1-i均不是可逆元，故2在Z[i]中不是既约元，显然也不是素元。

5.3整环中的因子分解一些基本概念对于一般的有单位元的交换环，既约元与素元往往是两个不同的概念。例如：在Z6中，[2]是素元，但不是既约元，因为[2]=[2][4]，从而[2]和[4]是[2]的真因子。

，其中3是不可约元，但是3不是素元，因为：5.3整环中的因子分解一些基本概念但是如果在有单位元的整环中，既约元与素元的关系有以下定理：5.3整环中的因子分解一些基本概念定理5.3.1：设D是有单位元的整环，则D中的素元必是既约元。证明：设p是素元且p=ab，则由p=ab可得p|ab，而由p是素元可得p|a或p|b若p|a，则由p=ab可得a|p，即p~a，因而b

U(D)。若p|b，则由p=ab可得b|p，即p~b，因而a

U(D)。即a与b中总有一个可逆元，所以p是既约元。

5.3整环中的因子分解一些基本概念那么，定理5.3.1的逆定理是否成立呢？为了给出定理5.3.1的逆定理成立的条件（即既约元是素元的条件），我们需要引出如下定义：注：定理5.3.1给出了素元是既约元的条件，这里我们所说的逆定理是指要研究既约元是素元的条件。5.3整环中的因子分解一些基本概念定义5.3.3：设D是有单位元的整环，a,b

D，若存在d

D使得以下两个条件成立，则称d是a和b的最大公因子。1）d|a，d|b；2）d’

D，若d’|a且d’|b，则d’|d。注：最大公因子跟我们在数论部分所说的最大公因数类似，但是有区别。5.3整环中的因子分解一些基本概念由定义5.3.3可以得到最大公因子的以下简单性质：5.3整环中的因子分解一些基本概念引理5.3.1：a与b的任意两个最大公因子是相伴的。证明：若d是a与b的最大公因子，则u

U(D)，ud也是a与b的最大公因子，即a与b的任意两个最大公因子是相伴的。注：上述引理表明最大公因子不唯一，因而以下当a与b的最大公因子存在时，以(a,b)表示a与b的任意一个最大公因子。

5.3整环中的因子分解一些基本概念引理5.3.2：(a,(b,c))~((a,b),c)。证明：设dl=(a,(b,c))，d2=((a,b),c)，则dl|a且dl|(b,c)进而dl|a，dl|b则dl|(a,b)又dl|c，因而d1|((a,b),c)=d2类似d2|d1，所以d2～d1，即(a,(b,c))~((a,b),c)5.3整环中的因子分解一些基本概念引理5.3.3：c(a,b)~(ca,cb)=(ac,bc)。证明：令d=(a,b)，d1=c(a,b)=cd，d2=(ca,cb)，则d1=cd|ca和d1=cb得d1|d2令d2=ud1，ca=xd2，则ca=xud1=xucd故a=xud5.3整环中的因子分解一些基本概念类似地，若令cb=yd2，可得b=yud因而ud|(a,b)=d得u~1由d2=ud1可知，d2|d1所以d1～d2，即c(a,b)~(ca,cb)=(ac,bc)5.3整环中的因子分解一些基本概念引理5.3.4：若(a,b)~1，(a,c)~1，则(a,bc)~1。证明：由于(a,bc)=((a,ac),bc)，又由引理5.3.2知((a,ac),bc)~(a,(ac,bc))即存在v

U(D)，使得((a,ac),bc)=v(a,(ac,bc))由引理5.3.3知(ac,bc)~c(a,b)，即存在m

U(D)，使得(ac,bc)=mc(a,b)5.3整环中的因子分解一些基本概念而由(a,b)~1，知存在u

U(D)，使得(a,b)=u因而(ac,bc)=mcu进而(a,bc)=v(a,(ac,bc))=v(a,mcu)=v(a,muc)又(a,c)~1，故存在w

U(D)，使得(a,c)=w。5.3整环中的因子分解一些基本概念下证(a,c)~(a,muc)首先由(a,c)=w知w|a，w|c因而w|a，w|muc即w是a与muc的公因子，因而w|(a,muc)又令(a,muc)=s，则s|a，s|muc5.3整环中的因子分解一些基本概念由于mu为可逆元，因而s|c故s|(a,c)，即(a,c)~(a,muc)故存在x

U(D)，使得x(a,c)=(a,muc)，因而(a,bc)=v(a,muc)=vx(a,c)=xvw由于x，v与w，都是可逆元，因而它们的乘积仍然是可逆元，故(a,bc)~15.3整环中的因子分解一些基本概念定理5.3.2：设D是有单位元的整环，若a,b

D，(a,b)存在，则D中的每个既约元也是素元。证明：设p是D中的既约元，并设p|ab，若p不是素元，则p∤a且p∤b若p∤a，令(p,a)=d，则d|a且d|p即在D中存在元素c与e，使得a=dc且p=de5.3整环中的因子分解一些基本概念由p是D中的既约元，得到d

U(D)或e

U(D)若e

U(D)，则d=pe-1，因而a=pe-1c即p|a矛盾，故d

U(D)，即d=(p,a)~15.3整环中的因子分解一些基本概念同理若p∤b，则(p,b)~1由引理5.3.4知(p,ab)~1另一方面，由p|ab，可知(p,ab)~p结合(p,ab)~1，知p~1这与p不是可逆元矛盾。此矛盾表明p|a或p|b。5.3整环中的因子分解唯一分解整环本小节主要讨论环中的一个元素能否唯一地分解为既约元之积的问题，这与方程求解问题关系密切。5.3整环中的因子分解唯一分解整环定义5.3.4：设D是有单位元的整环，若a

D*\U(D)1）a可分解为有限个既约元之积，即a=p1p2…ps，其中pi，i=1,2,…,s，为既约元。2）若a=p1p2…ps=q1q2…qt，其中pi，1≤i≤s，qj，1≤j≤t，均为既约元，则s=t，且适当调换次序后可以使得pi~qi（1≤i≤s），则称D是唯一分解整环(UniqueFactorizationDomain,UFD)。由定理5.3.2知唯一分解整环有以下重要性质：5.3整环中的因子分解唯一分解整环定理5.3.3：设D是唯一分解整环，则D中任何两个不全为0的元素均有最大公因子，因而D中每一个既约元也是素元。

5.3整环中的因子分解唯一分解整环定理5.3.4：设D是有单位元的整环，则以下三个命题等价：1）D是唯一分解整环。2）D满足下列两条件：a）D中的任意真因子序列a1,a2,…,ai,…(其中ai+1是ai的真因子)只能含有有限项。b）D中任何两元素均有最大公因子。3）D满足下列两条件：a）D中的任意真因子序列a1,a2,…,ai,…(其中ai+1是ai的真因子)只能含有有限项。b）D中每一既约元都是素元。5.3整环中的因子分解唯一分解整环证明：1)→2)：由于D是唯一分解整环，a1只能分解为有限个既约元之积，因而a1的真因子序列只有有限项，条件a)满足，由定理5.3.3知条件b)也满足。2)→3)：由定理5.3.3可得。5.3整环中的因子分解唯一分解整环3)→1)：设a是D*\U中任一元素，首先证明a可分解为有限个既约元之积。若a是既约元，则得证；否则a可分解为a=p1a1，其中p1为既约元。再对a1作同样的分解，则或a1是既约元（结论得证），或a1=p2a2，其中p2为既约元（继续分解）。如此，可得真因子序列a,a1,…。由条件a)该序列必终止于有限项，设as=ps+1是既约元，则a=p1p2…psps+1。再证分解式的唯一性：设a=p1p2…ps=q1q2…qt。对分解式中因子的个数s作数学归纳。5.3整环中的因子分解唯一分解整环s=1时a=p1为既约元，不可能再分解为两个以上的既约元的乘积，故t=1，a=p1=q1。假设结论对s-1成立。当a=p1p2…ps=q1q2…qt时，p1|q1q2…qt，由于p1是素元，故必有某个qk使p1|qk，由于qi的次序可任意排列，不妨设p1|q1，于是q1=up1，又q1也是既约元，故u

U(D)，即p1~q1，将q1=up1代入a的分解式，并消去p1得到a’=p2p3…ps=(uq2)q3…qt，由归纳假设，得s=t，并适当排列次序后可得pi~qi（2≤i≤s）。因此结论对任何正整数s均成立。5.3整环中的因子分解唯一分解整环例5.3.3：由高等代数知识知整数环Z和数域F上的多项式环均满足唯一分解整环的定义，因而都是唯一分解整环，且每一既约元都是素元。而环，即由所有形如的元素构成的集合中，并不是任意两个元素都有最大公因子，因而不是唯一分解整环。例如取则容易验证(a,b)就不存在。5.3整环中的因子分解唯一分解整环在非唯一分解环内，通常的一些代数方程的性质不一定成立。例如，容易验证在Z12中，[2],[4],[8],[10]都是二次方程x2-4=0的根，即二次方程x2-4=0的根不只有两个根而有4个根。但是，在唯一分解整环内容易证明有如下结论：5.3整环中的因子分解唯一分解整环引理5.3.5：在唯一分解整环内，n次代数方程最多有n个根。利用这一性质可以证明以下定理。5.3整环中的因子分解唯一分解整环定理5.3.6：域的乘群的任何有限子群是循环群。证明：设G是域F的有限子乘群，令m是G中所有元素的阶的最小公倍数，由拉格朗日定理：G中任意元素的阶均为群G的阶的因子，因而若设c为G中阶为m的元素（为什么可以这样假设？理由见下一章），则m≤|G|另一方面，G中的元素均满足方程xm-l=0，而多项式f(x)=xm-l

F[x]在F上最多有m个不同的根，故|G|≤m，由此得|G|=m，所以G=(c)。5.3整环中的因子分解唯一分解整环下面介绍两种特殊的唯一分解整环：1、主理想整环（PrincipalIdealDomain,PID）2、欧几里得整环5.3整环中的因子分解唯一分解整环1、主理想整环如果理想中的一切元素都是由一个元素的倍数及其线性组合生成，则称这个理想为主理想，具体定义如下：5.3整环中的因子分解唯一分解整环1、主理想整环定义5.3.5：在可换环R中，由一个元素a

R所生成的理想I(a)={ra+na|r

R,n

Z}称为环R的一个主理想，称元素a为该主理想的生成元。注：运算ra表示环中的乘法运算，na表示加法的幂次运算。5.3整环中的因子分解唯一