第四章多项式环与有限域

1、第第4章章 多项式环与有限域多项式环与有限域 第第4章章 多项式环与有限域多项式环与有限域 4.1 4.1 子环与理想子环与理想 4.2 4.2 多项式剩余类环多项式剩余类环 4.3 4.3 循环群循环群 4.4 4.4 有限域有限域(Galoias(Galoias域域) )的乘法结构的乘法结构 4.5 4.5 有限域的加法结构有限域的加法结构 4.6 4.6 有限域的代数结构与多项式的因式分有限域的代数结构与多项式的因式分解解 习题习题 第第4章章 多项式环与有限域多项式环与有限域 4.1 子子 环环 与与 理理 想想 一、一、 子环子环 类似于子群，类似于子群， 在环中也可定义子环。在环中

2、也可定义子环。 定义定义4.1.1 若环中的子集若环中的子集S， 关于关于R中的代数运算也中的代数运算也构成环，构成环， 则称则称S是是R的子环，的子环， R为为S的扩环。的扩环。 定理定理4.1.1 非空子集非空子集S是是R的子环的充要条件是：的子环的充要条件是： (1) 对任何两个元素对任何两个元素a,bS， 恒有恒有a-bS； (2) 对任何对任何a,bS， 恒有恒有abS。 第第4章章 多项式环与有限域多项式环与有限域 证明证明 若若S是是R的子环，的子环， 则由环的定义可知，则由环的定义可知， 条件条件(1)、 (2)显然成立。显然成立。 若条件若条件(1)、 (2)成立，成立， 则

3、由定理则由定理2.4.2可知，可知， S对环对环R中的加法运算构成可换子群，中的加法运算构成可换子群， 并且并且S关于关于R的乘法封的乘法封闭。闭。 由于由于S是环中的子集，是环中的子集， 因此因此R中的乘法结合律，中的乘法结合律， 加法和乘法间的分配律在加法和乘法间的分配律在S中自然成立，中自然成立， 由此可知由此可知S是是一个环。一个环。 第第4章章 多项式环与有限域多项式环与有限域 例例4.1 全体整数集合构成一个可换环。全体整数集合构成一个可换环。 以某一整数以某一整数m的倍数全体构成其中的一个子集，的倍数全体构成其中的一个子集， 该子集就是整数该子集就是整数环中的一个子环。环中的一个

4、子环。 如如m=3， 则所有则所有3的倍数的全体集的倍数的全体集合合0， 3， 6， 9， 构成一个子环。构成一个子环。 一个环至少有两个子环，一个环至少有两个子环， 一个是由一个是由0元素组成，元素组成， 一个是环一个是环R本身，本身， 称此两个子环为环称此两个子环为环R的的假子环假子环， 其其余的称为余的称为真子环真子环。 第第4章章 多项式环与有限域多项式环与有限域 二、二、 理想理想 理想理想是很重要的一类子环，是很重要的一类子环， 它在环中的作用相当它在环中的作用相当于正规子群在群中的作用。于正规子群在群中的作用。 定义定义4.1.2 设设R是交换环是交换环， I是是R的非空子集，的

5、非空子集， 若若 (1) 对任意两个元素对任意两个元素a,bI， 恒有恒有a-bI； (2) 对任意对任意aI， rR， 恒有恒有ar=raI， 则称则称I是是R中的一个理想。中的一个理想。 第第4章章 多项式环与有限域多项式环与有限域 由此定义可知，由此定义可知， 理想理想其实就是其实就是可换环可换环中的一个子环中的一个子环， 该子环也称双边子环。该子环也称双边子环。u由由(1)可知可知I是一个阿贝尔加群是一个阿贝尔加群u由由(2)可知可知I的某些元素都由某一元素的某些元素都由某一元素a的倍数组成。的倍数组成。 因因此，此， 若理想中包含了元素若理想中包含了元素a， 则它就包含了则它就包含了

6、a的一切倍的一切倍元。元。 u由于由于I构成一个可换加群，构成一个可换加群， 所以可用它作为一个正规子所以可用它作为一个正规子群，群， 把把R中的元素进行分类划分陪集中的元素进行分类划分陪集。 第第4章章 多项式环与有限域多项式环与有限域 例例4.2 全体整数全体整数 Z 构成一个可换环，构成一个可换环， 某一整数某一整数m的的倍数构成一个理想倍数构成一个理想Im， 以此理想可把全体整数以此理想可把全体整数 Z 划分划分陪集。陪集。 如如m=5， 则则 I5： 0， 5， 10， 15， ， 划分陪集如下：划分陪集如下： 0 : 0， 5， -5， 10， -10， 1 : 1， 6， -4，

7、 11， -9， 2 : 2， 7， -3， 12， -8， 3 : 3， 8， -2， 13， -7， 4 : 4， 9， -1， 14， -6， 第第4章章 多项式环与有限域多项式环与有限域 由正规子群的理论可知，由正规子群的理论可知， 这些陪集全体这些陪集全体0 ， 1 ,2 ,3 ,4 构成一个模构成一个模5的阿贝尔加群，的阿贝尔加群， 称为称为模模5的剩余类群，的剩余类群， 用用Z (mod 5)表示；表示； 一般情况用一般情况用R (mod I)表示之。表示之。 若若R中任二元素中任二元素a、 b属于属于I的同一剩余类，的同一剩余类， 则称则称a、 b对模对模I同余，同余， 记为记

8、为 ab (mod I)或或 a-b0 (mod I)第第4章章 多项式环与有限域多项式环与有限域 定理定理4.1.2 设设R是是可换环可换环， I为为R的一个的一个理想理想， 于于是是R模模I构成一个可换环，构成一个可换环， 称它为称它为环环R以理想以理想I为模的剩为模的剩余类环余类环M。 证明证明 (1) 对任意对任意a,bM， 一定存在有元素一定存在有元素a,bR， 且且a=a+I， b=b+I。 所以所以 a-b=a+I-(b+I)=a-b+(I-I)=c+I=cM 由定理由定理2.4.2可知可知M构成阿贝尔加群。构成阿贝尔加群。 第第4章章 多项式环与有限域多项式环与有限域 (2)

9、乘法封闭性成立，乘法封闭性成立， 交换律成立。交换律成立。 对一切元素对一切元素a， bM， 恒有恒有 ab=ab =ab+IM ab=ab = ba =ba (3) 结合律成立结合律成立 (ab)c=(ab )c= (ab)c =a(bc) =a( bc )=a( bc ) 由此可知由此可知M组成一可换环。组成一可换环。 第第4章章 多项式环与有限域多项式环与有限域 定义定义 4.1.3 在可换环在可换环R中，中， 由一个元素由一个元素aR所生所生成的理想成的理想I(a)=ra+narR， nZ称为环称为环R的一的一个主理想，个主理想， 称元素称元素a为该为该主理想的生成元主理想的生成元。

10、在例在例4.2中，中， 以某一整数以某一整数m的倍数所构成的理想的倍数所构成的理想Im就是一个主理想，就是一个主理想， m是生成元。是生成元。 如果如果R是一个有单位是一个有单位元素的无零因子可换环，元素的无零因子可换环， 且且R中的每一理想都是主理中的每一理想都是主理想，想， 则称该则称该R为主理想环。为主理想环。 例如，例如， 整数环整数环 Z 就是一个就是一个主理想环。主理想环。 第第4章章 多项式环与有限域多项式环与有限域 4.2 多项式剩余类环多项式剩余类环 一、一、 多项式的基本性质多项式的基本性质 定义定义4.2.1 含有一个未定元数含有一个未定元数x的域的域Fp(GF(p)上的

11、上的多项式定义为多项式定义为 f(x)=fnxn+f n-1 x n-1 +f1x+f0 fiFp i=0， 1， 2， ， n 且用且用Fpx(或或GF(p)x)表示系数取自域表示系数取自域Fp上上 的一切多项式集合。的一切多项式集合。 第第4章章 多项式环与有限域多项式环与有限域 多项式次数：多项式次数： 称系数不为零的称系数不为零的x的最高次数为多项的最高次数为多项式式f(x)的次数，的次数， 记为记为f(x)(f)或或deg f(x)(deg f)。 由此由此可知，可知， 若若fn0， 则则f(x)=n， 称称f(x)为为n次多项式。次多项式。 若若fn=f n-1 =f k-1 =0

12、， fk0,则则f(x)=k， 称称f(x)为为k次多项次多项式。式。 第第4章章 多项式环与有限域多项式环与有限域 首一多项式首一多项式： 最高次数的系数为最高次数的系数为1的多项式称为首的多项式称为首一多项式。一多项式。 下面定义多项式之间的相等、下面定义多项式之间的相等、 相乘和相加规则。相乘和相加规则。 设设 f(x)=fnxn+f n-1 x n-1 +f1x+f0 fiFp g(x)=gnxn+g n-1 x n-1 +g1x+g0 giFp 若对所有若对所有 fi=gi i=0， 1， 2， ， n 则称则称f(x)=g(x)。 第第4章章 多项式环与有限域多项式环与有限域 多项

13、式的相加运算为多项式的相加运算为 f(x)+g(x) =(fn+gn)xn+(f n-1 +g n-1 )x n-1 +(f1+g1)x+(f0+g0) 多项式多项式f(x)=fnxn+f1x+f0与与g(x)=gmxm+g1x+g0的相乘运算为的相乘运算为 f(x)g(x)=h n+m x n+m +h n+m-1 x n+m-1 +h1x+h0 第第4章章 多项式环与有限域多项式环与有限域 式中式中 nmijjijijjijinmmmigfmnmigfh, 2, 1, 2 , 1 , 00第第4章章 多项式环与有限域多项式环与有限域 定理定理4.2.1 按以上定义的多项式运算，按以上定义的

14、多项式运算， Fpx 构成一个具有单位元素、构成一个具有单位元素、 无零因子的可换环。无零因子的可换环。 证明证明 (1) Fpx 关于加法构成可换群。关于加法构成可换群。 1 封闭性显然成立。封闭性显然成立。 2 零元为零元为 f(x)=0。 3 f(x)=fnxn+f n-1 x n-1 +f1x+f0的逆元为的逆元为 -f(x)=-fnxn-f n-1 x n-1 -f1x-f0。 第第4章章 多项式环与有限域多项式环与有限域 4 交换律和结合律显然成立。交换律和结合律显然成立。 (2) 乘法封闭性成立。乘法封闭性成立。 乘法单位元是乘法单位元是 f(x)=1。 (3) 无零因子。无零因

15、子。 设设 f(x)0， g(x)0， 令令f、 g分别是分别是f(x)和和g(x)的的最高次数的系数，最高次数的系数， 即即f0、 g0。 因此因此 fg0 fgFp 因为域因为域Fp无零因子，无零因子， 而而fg是是 f(x)g(x) 的最高次数的最高次数项，项， 且不为且不为0， 故故 f(x)g(x)0 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.2.2 给定任意两个多项式给定任意两个多项式 f(x)g(x)Fpx ， 一定存在有唯一的多项式一定存在有唯一的多项式 q(x)和和r(x) 使使 f(x)=q(x)g(x)+r(x) 0r(x)g(x) 或或 r(x)=0 该

16、定理的证明与定理该定理的证明与定理2.1.2(欧几里德除法欧几里德除法)的证明完的证明完全类似，全类似， 这里不再重复。这里不再重复。 第第4章章 多项式环与有限域多项式环与有限域 二、二、 既约多项式既约多项式 与与 Z 环上的素数相对应，环上的素数相对应， 在在 Fpx 上有既约多上有既约多项式。项式。 定义定义4.2.2 设设 f(x) 是次数大于零的多项式，是次数大于零的多项式， 若除若除了常数和常数与本身的乘积以外，了常数和常数与本身的乘积以外， 再不能被域再不能被域Fp上的上的其它多项式除尽，其它多项式除尽， 则称则称 f(x) 为域为域Fp上的既约多项式。上的既约多项式。 第第4

17、章章 多项式环与有限域多项式环与有限域 由上述定义可得出：由上述定义可得出： 1 一个常数总是多项式的因子。一个常数总是多项式的因子。 例如，例如， 实数域实数域上的多项式上的多项式 3x2+1=3(x2+1/3)， 由此可知由此可知3是是3x2+1多项多项式的一个因子。式的一个因子。 2 f(x) 是否既约与讨论的域有很大关系。是否既约与讨论的域有很大关系。 例如，例如， f(x)=x2+1 ， 在实数域上是既约的；在实数域上是既约的； 但在复数域上就但在复数域上就可以分解为可以分解为 f(x)=(x+i)(x-i)。 第第4章章 多项式环与有限域多项式环与有限域 判别判别 f(x)(f0)

18、是否既约的方法是：是否既约的方法是： f(x) 既约的充既约的充要条件是要条件是 f(x) 不能再分解成两个次数低于不能再分解成两个次数低于f(x) 的多项的多项式的乘积。式的乘积。 所以，所以， 不论在哪一域上，不论在哪一域上， 凡是一次首一凡是一次首一多项式都是既约多项式。多项式都是既约多项式。 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.2.3 每一个首一多项式每一个首一多项式 f(x) 必可分解为首必可分解为首一既约多项式之积，一既约多项式之积， 并且当不考虑因式的顺序时，并且当不考虑因式的顺序时， 这这种分解是唯一的，种分解是唯一的， 即即 式中，式中， pi(x) 为

19、首一既约多项式，为首一既约多项式， i是某一正整数，是某一正整数， i=1， 2， ， s。 ixpxpxpxfi)()()()(2121第第4章章 多项式环与有限域多项式环与有限域 推论推论4.2.1 d次多项式次多项式 f(x) 不可能有多于不可能有多于d个的一次因式。个的一次因式。 定理定理4.2.4 为多项式为多项式 f(x) 之根的充要条件是：之根的充要条件是： (x-)f(x) 证明 由多项式的欧几里德除法可知 f(x)=q(x)(x-)+r(x)=q(x)(x-)+r r(x) (x-) 若是 f(x) 的根， 则 f()=q()(x-)+r=0 可知r=0， 故 f(x)=q(

20、x)(x-) (x-)f(x) 第第4章章 多项式环与有限域多项式环与有限域 反之， 若 (x-)f(x) ， 则 f(x)=q(x)(x-) 因为-=0， 故是x-的根， 由此 f()=q()(-)=0 也是 f(x) 的根。 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.2.5 d次多项式至多有次多项式至多有d个根。个根。 证明 假定d次多项式 f(x) 有多于d个根， 则由定理4.2.3和定理4.2.4可知， f(x) 应当有多于d个的一次因式， 这与推论4.2.1相矛盾。 定理4.2.6 若p(x)是f(x)的k重既约因式， 则p(x)必是f(x)的导数f(x)的k-1重既

21、约因式。 第第4章章 多项式环与有限域多项式环与有限域 三、 最大(高)公因式 定义4.2.3 若 (f(x)， g(x)， ， k(x)是同时除尽多项式f(x)， g(x)， ， k(x)的次数最高的首一多项式， 则称(f(x)， g(x)， ， k(x)是f(x)， g(x)， ， k(x)的最大公因式， 用(f(x)， g(x)， ， k(x)或 GCD f(x)， g(x)， ， k(x) 表示之。 第第4章章 多项式环与有限域多项式环与有限域 与整数的最大公约数相似， 可用同样的方法证明多项式的最大公因式有如下性质： 1 由欧几里德除法可知， 若f(x)g(x)， 则 f(x)=g(

22、x)q(x)+r(x) 0 r(x)q(x) 或 r(x)=0 可得 (f(x)， g(x)=(g(x)， r(x)。 第第4章章 多项式环与有限域多项式环与有限域 2 由整数的欧几里德算法， 同样有多项式的欧几里德算法： (f(x)， g(x)=A(x)f(x)+B(x)g(x) 式中 0A(x)g(x)-(f(x)， g(x) 0B(x)f(x)-(f(x)， g(x) 该算法将在以后详细证明。 第第4章章 多项式环与有限域多项式环与有限域 四、 最小(低)公倍式 定义4.2.4 若 f(x)， g(x)是同时能被g(x)、 f(x)除尽的次数最低的首一多项式， 则称f(x)， g(x)是

23、g(x)和f(x)的最小公倍式， 用f(x)， g(x)或LCMf(x)， g(x)表示之。 第第4章章 多项式环与有限域多项式环与有限域 与整数的最小公倍数完全相似， 多项式的最小公倍式也有如下性质： 1 f(x)， g(x)， k(x)多项式集合中， 若两两互素， 则f(x)， g(x)， k(x)=f(x)g(x)k(x)； 2 f(x)， g(x)的最小公倍式f(x)， g(x)能除尽 f(x)， g(x) 的一切公倍式； 3 f(x)g(x)=f(x)， g(x)(f(x)， g(x)。 或 )(),()()()(),(xgxfxgxfxgxf第第4章章 多项式环与有限域多项式环与有

24、限域 由上面的讨论可知， 由于Fp上多项式全体与整数全体均构成一可换环， 因此多项式的理论与整数的理论是完全平行的。 多项式相当于一般的整数， 既约多项式相当于素数， 而常数(零次多项式)相当于整数中的1， 它既不是既约多项式也不是可约多项式。 多项式与整数的这种平行关系， 在下面讨论中还将看到。 第第4章章 多项式环与有限域多项式环与有限域 五、五、 多项式剩余类环与有限域的构造多项式剩余类环与有限域的构造 如同整数的剩余类环一样，如同整数的剩余类环一样， 以一个以一个Fp上的多项式：上的多项式： f(x)=f0+f1x+fnxn f(x)0 为模的剩余类全体也构成一个环，为模的剩余类全体也

25、构成一个环， 称为称为多项式剩余类多项式剩余类环环。 如同整数剩余类环的构造，如同整数剩余类环的构造， 我们首先在我们首先在 FpX上上寻找一个理想寻找一个理想， 然后然后以此理想为模以此理想为模对全体对全体多项式分类，多项式分类， 就得到一个剩余类环。就得到一个剩余类环。 理想的寻找理想的寻找第第4章章 多项式环与有限域多项式环与有限域 例子例子4.4 P107第第4章章 多项式环与有限域多项式环与有限域 引理引理4.2.1 Fpx上任一多项式上任一多项式f(x)的一切倍式集的一切倍式集合合If(x) 组成一个理想。组成一个理想。 证明 设 f(x)=f0+f1x+fnxn f(x)0 要证

26、明 f(x) 的一切倍式集合If(x)是一理想， 只要证明： (1) 对一切a(x)， b(x)If(x)， 有a(x)-b(x)If(x)。 (2) 对任意c(x)Fpx， a(x)If(x)有c(x)a(x)If(x)。 第第4章章 多项式环与有限域多项式环与有限域 现证明如下： (1) 因为a(x)， b(x)If(x)， 所以 a(x)=a1(x)f(x)b(x)=b1(x)f(x) 因而 a(x)-b(x)=f(x)(a1(x)-b1(x)If(x) (2) c(x)a(x)=c(x)a1(x)f(x)=d(x)f(x)If(x) 由此可知 If(x) 是一个理想。 第第4章章 多项

27、式环与有限域多项式环与有限域 定义定义4.2.5 若若 Fpx中的两多项式中的两多项式a(x)、 b(x)被同一被同一多项式多项式f(x) 除时有相同的除时有相同的 余式：余式： a(x)= q1(x)f(x)+r(x) b(x)= q2(x)f(x)+r(x) 0 r(x) f(x) 则称则称 a(x)、 b(x)关于模关于模f(x) 同余，同余， 记为记为 a(x)b(x) (mod f(x) 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.2.7 a(x)b(x) (mod f(x) 的充要条件是：的充要条件是： a(x)-b(x)=q(x)f(x) 或或 f(x)a(x)-b

28、(x) 证明 若 a(x)b(x) (mod f(x)， 则a(x)与b(x)属于同一剩余类中， 设属于b(x) 的剩余类中： a(x) b(x) =b(x)+If(x) 或 a(x)=b(x)+f(x)q(x) q(x)fp(x) 所以 a(x)-b(x)=f(x)q(x) 或 f(x) a(x)-b(x) 第第4章章 多项式环与有限域多项式环与有限域 反之， 若 a(x)-b(x)=f(x)q(x) 则 a(x)=b(x)+f(x)q(x)b(x)+If(x)= b(x) 所以 a(x)b(x) (mod f(x) 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.2.8 以以 f

29、(x)为模的多项式剩余类全体，为模的多项式剩余类全体， 组成一组成一个有单位元的可换环个有单位元的可换环Fpx/f(x)。 为了证明此定理， 我们首先规定两个陪集或剩余类之间的运算如下。 (1) 加法 a(x) + b(x) =a(x)+b(x) 因为 a(x) =a(x)+If(x) b(x) =b(x)+If(x) 第第4章章 多项式环与有限域多项式环与有限域 所以 a(x) + b(x) = a(x)+If(x)+b(x)+If(x) = a(x)+b(x)+If(x)=a(x)+b(x) (2) 乘法 a(x) b(x) = (a(x)+If(x)(b(x)+If(x) = a(x)b

30、(x)+If(x)=a(x)b(x) 第第4章章 多项式环与有限域多项式环与有限域 example P109 第第4章章 多项式环与有限域多项式环与有限域 定理定理 4.2.9 若若n(0)次首一多项式次首一多项式f(x)在域在域GF(p)上既上既约，约， 则由则由f(x)为模所组成的多项式剩余类环是一个有为模所组成的多项式剩余类环是一个有 pn个元素的有限域个元素的有限域GF(pn)。 证明 用 f(x)去除任一多项式， 所得余式r(x)的次数低于f(x)=n， 因此所有次数低于n次多项式必处在不同的剩余类中。 所以， 下面只要证明每一个次数小于n次的多项式g(x) 都有逆元即可。 注意比较

31、：多项式剩余类环与有限域的构造条件的区 别第第4章章 多项式环与有限域多项式环与有限域 六、六、 多项式主理想环多项式主理想环 定理4.2.1证明了域Fp上的所有多项式全体 Fpx ， 是一个有单位元的可换环， 引理4.2.1说明了该多项式环上理想的构造。 下面讨论主理想的构造。 第第4章章 多项式环与有限域多项式环与有限域 引理 4.2.2 多项式环 Fpx 中的一切理想均是主理想。 证明 设 Ifx是Fpx的任一理想。 若Ifx仅由零多项式构成， 它显然是主理想。 若Ifx中含有非零多项式， 则其中必含有一个次数最低的多项式f(x)。 设a(x)是Ifx 中任一多项式， 由欧几里德除法可知

32、： a(x)=q(x)f(x)+r(x) 0 r(x) f(x) 或 r(x)=0 第第4章章 多项式环与有限域多项式环与有限域 由理想定义可知： r(x)=a(x)-q(x)f(x)Ifx 由于 f(x) 是理想中次数最低的多项式， 且由r(x)的次数或者等于0或者小于f(x)。 可知， r(x)的次数只能等于0， 且由无0多项式的假设可知r(x)=0。 因此， a(x)=q(x)f(x)Ifx 。 第第4章章 多项式环与有限域多项式环与有限域 引理4.2.2中的 f(x) 为主理想的生成元， 或生成多项式。 当假定生成多项式为首一多项式时， 多项式理想中的生成多项式显然是唯一的。 由引理4

33、.2.1和引理4.2.2可知， Fpx 不仅是一个有单位元可换环， 而且也是一个主理想环。 第第4章章 多项式环与有限域多项式环与有限域 定理4.2.10 多项式剩余类环 Fpx/f(x)中每一理想皆为主理想， 且该主理想的生成多项式必除尽f(x) 。 证明 该定理前半部分证明完全类似于引理4.2.2的证明， 这里不再重复。 设I是 Fpx/f(x)中任一理想， g(x) 是它的生成多项式。 第第4章章 多项式环与有限域多项式环与有限域 七、 同构与自同构 由上面讨论看到， 以某一素数p为模的剩余类， 和以某一Fp上的既约多项式 p(x) 为模的多项式剩余类之间， 有几乎完全相同的结构和性质。

34、 一般， 有时两个集合之间的元素不但有一一对应的关系， 而且有完全相同的性质和结构。例如， Fp上的n-1次多项式与Fp上的n重之间的每个元素， 均存在一一对应关系。 例如， GF(2)上的二次多项式与GF(2) 上的三重， 它们元素之间有如下一一对应关系： 第第4章章 多项式环与有限域多项式环与有限域 二次多项式 三重0+0 x+0 x2 0001+0 x+0 x2 1000+x+0 x2 0101+x+0 x2 1100+0 x+x2 0011+0 x+x2 1010+x+x2 0111+x+x2 111 第第4章章 多项式环与有限域多项式环与有限域 定义 4.2.6 设G=1， a， b

35、， 为乘(加)群， 而G是一个定义了乘(加)法运算的集合(不必封闭)， G中乘(加)法用表示， G中乘(加)法用*表示。 若在G与G间建立了一一对应关系， 把G中元素1， a， b， 变成G中元素1， a， b， ， 且对任意a， bG有 (ab)=(a)*(b) 称群G与集合G为群同构。 第第4章章 多项式环与有限域多项式环与有限域 由此可知， 群同构是G与G之间的一种一一对应关系， 对任何G中的元素a， 恒有a a， 或(a)=a， abab， 即不仅元素之间有一一对应关系， 而且运算结果也一一对应。第第4章章 多项式环与有限域多项式环与有限域 定理 4.2.11 假定群G与G同构， 则G

36、亦为群。 证明： (1) 封闭性成立。 设 a， bG， (a)=a， (b)=b， a， bG。 由定义知， (a b)=(a)*(b)=a*b， 因为a bG， 所以a b的像(a b)=a*b也必在G中， 故a*bG。 第第4章章 多项式环与有限域多项式环与有限域 (2) 结合律成立。 设a， b， cG， 则 (a*b)*c =(a b)*(c)=(a b) c) =(a (b c) =(a)*(b c)=a*(b*c) (3) 有单位元。 (1)=1即为单位元。 因为对任一aG， 有a*1=(a 1)=(a)=a。 第第4章章 多项式环与有限域多项式环与有限域 (4) 有逆元。 对任

37、一个 aG， 令a-1 =(a-1 )。 所以 a*a-1 =(a)*(a-1 ) = (a a -1 )=(1)=1。 第第4章章 多项式环与有限域多项式环与有限域 同群一样， 在环和域等代数系统中也可建立同构。 且也可证明若G是环或是域， 则G也是环或域； 当然在这种情况下， 必须建立两种运算(加和乘)的对应关系。 若G=G， 则称为自同构， 称为群G到自身的映射。 因此， 自同构是集合自身到自身的映射。 第第4章章 多项式环与有限域多项式环与有限域 4.3 循循 环环 群群 有限域在编码理论中起着非常重要的作用。有限域在编码理论中起着非常重要的作用。 由第二章由第二章可知，可知， 所谓有

38、限域就是域中元素的个数是有限的，所谓有限域就是域中元素的个数是有限的， 元元素的个数称为域的阶，素的个数称为域的阶， 若为若为p阶有限域，阶有限域， 用用 GF(p)或或Fp表示。表示。 而循环群的概念则是了解有限域的基础，而循环群的概念则是了解有限域的基础， 它在编码理论中，它在编码理论中， 特别在循环码理论中起关键作用。特别在循环码理论中起关键作用。 第第4章章 多项式环与有限域多项式环与有限域 一、一、 循环群的基本概念循环群的基本概念在定义循环群以前，在定义循环群以前， 先看以下例子。先看以下例子。 例例4.6 考虑以下复数域上的三次方程。考虑以下复数域上的三次方程。 x3-1=0 它

39、在复数域上有它在复数域上有3个根：个根： x0= 1 x1= e (23)i =cos(2/3)+i sin(2/3) x2= e(43)i =cos(4/3)+i sin(4/3) 第第4章章 多项式环与有限域多项式环与有限域 显然，显然， 若取其中某一根若取其中某一根x1=e (23)i ， 则这则这3个根可个根可通过这一个根的各次幂表示。通过这一个根的各次幂表示。 x0= x01=1 x1= x11=e (23)i x2= x21=e (43)i 第第4章章 多项式环与有限域多项式环与有限域 事实上，事实上， 上述上述3个根个根x0、 x1、 x2构成阿贝尔乘群：构成阿贝尔乘群： 单位元

40、为单位元为x0， 封闭性成立，封闭性成立， 且且x1、 x2互为逆元，互为逆元， 交换交换律显然满足。律显然满足。 像这种群中的所有元素都可由一个元素像这种群中的所有元素都可由一个元素的连续运算的连续运算(在乘群为幂次表示在乘群为幂次表示)而产生的群，而产生的群， 称为循称为循环群，环群， 由此引入循环群的定义。由此引入循环群的定义。 第第4章章 多项式环与有限域多项式环与有限域 定义定义4.3.1 由一个单独元素的一切幂次所构成的群由一个单独元素的一切幂次所构成的群称为循环群，称为循环群， 该元素称为循环群的生成元。该元素称为循环群的生成元。 例例4.7 整数全体关于加法构成循环群，整数全体

41、关于加法构成循环群， 它的生成元它的生成元 是是1。 例如：例如： 5=1+1+1+1+1， 6=1+1+1+1+1+1， ， 这里所指的元素这里所指的元素1的幂次是指加法运算而言。的幂次是指加法运算而言。 15= 1+1+1+1+1=5 16= 1+1+1+1+1+1=6 由于整数群是一个无限群，由于整数群是一个无限群， 故这是一个无限循环群。故这是一个无限循环群。 第第4章章 多项式环与有限域多项式环与有限域 二、二、 循环群的构造及其性质循环群的构造及其性质 设设a是循环群中的任一个元素，是循环群中的任一个元素， 考虑考虑a的一切幂的一切幂an， 这时可能有两种情况：这时可能有两种情况：

42、 (1) a的所有幂次的所有幂次ah(h=0， 1， 2， 3， )均均不相同，不相同， 这时由这时由a生成的群生成的群 G(a)=a -2 ， a -1 ， a0， a1， a2中，中， 元素的个数无限，元素的个数无限， 称为无限循环群。称为无限循环群。 第第4章章 多项式环与有限域多项式环与有限域 (2) a的某二次幂相同，的某二次幂相同， 也就是存在有整数也就是存在有整数h、 k(且且hk)使使ah=ak， 于是有于是有 aha -k =aka -k =e a h-k =e h-k 为正整数为正整数 于是，于是， 群群 G(a) 的元素为：的元素为： e， a1， a2， ， a n=h

43、-k =e， a1， 。 群中元素个数有限，群中元素个数有限， 所以是有限所以是有限循环群。循环群。 称称an=e的最小正整数的最小正整数n为有限循环群元素为有限循环群元素a的的级。级。 若为无限循环群，若为无限循环群， 则则a是无限级的。是无限级的。 在有限循环在有限循环群中，群中， 有以下特点：有以下特点： 第第4章章 多项式环与有限域多项式环与有限域 1 a0=e， a， a2， ， a n-1 均互不相同。均互不相同。 若相若相反，反， ah=ak， 0khn， 则则 a h-k =e 0h-k=n1n 于是有于是有 a n1 =a h-k =e 0n1n 这与假设这与假设n是使是使a

44、n=e的最小正整数相矛盾。的最小正整数相矛盾。 第第4章章 多项式环与有限域多项式环与有限域 2 a为为n级元素，级元素， 即即an=e， 则则a的一切幂次生成的的一切幂次生成的元素都在元素都在G(a)=a0=e， a1， a2， ， a n-1 中。中。 设设m为为任意整数，任意整数， 由欧几里德除法有由欧几里德除法有 m=qn+r 0rn am=a qn+r =(an)qar=eqar=ear=ar 而而0rn， 所以所以a的一切幂均在的一切幂均在 G(a) 中。中。 3 凡是循环群必是可换群。凡是循环群必是可换群。 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.3.1 可换群

45、可换群G中的每一元素中的每一元素a皆能生成一个循皆能生成一个循环群，环群， 它是它是G的子群。的子群。 若若a是无限级元素，是无限级元素， 则生成的则生成的是无限循环群。是无限循环群。 如果如果a是有限级元素，是有限级元素， 则生成的是有则生成的是有限循环群，限循环群， 元素元素a的级就是有限循环群的阶数。的级就是有限循环群的阶数。 第第4章章 多项式环与有限域多项式环与有限域 三、三、 有限循环群中元素级的性质有限循环群中元素级的性质 1 若若aG是是n级元素级元素,则则am=e的充要条件是的充要条件是nm(m为整数为整数)。 证明 若am=e， 由欧几里德除法有 m=qn+r 0rn 则

46、am=e=a qn+r =a qn ar=(an)qar=ear=ar 所以am=ar=e， 而0rn， 这与n是a的级相矛盾， 故r=0， 由此m=qn， nm。 反之， 若nm， 则 am=a qn =(an)q=eq=e 第第4章章 多项式环与有限域多项式环与有限域 2 设设a， bG， a为为n级元素，级元素， b为为m级元素，级元素， 且且(n， m)=1， 则则(ab)之级等于之级等于nm。 3 若若a为为n级元素，级元素， 则则ak元素之级为元素之级为 n/(k， n) 。 第第4章章 多项式环与有限域多项式环与有限域 推论4.3.1 若a为dk级元素， 则ak为d级元素。 证明

47、 a dk =(ak) d=e 推论4.3.2 n阶循环群中， 每个元素的级是群阶数n的因子。 此推论直接由性质3得到。 由性质3可知， 群中每一元素ai的级为 n/(i， n)， 若(n， i)=1， 则ai元素的级亦为n， 也就是说由ai的幂次亦可生成循环群G(a) 中的全部元素： (ai) 0=e， ai， a 2i ， ， a i(n-1) 第第4章章 多项式环与有限域多项式环与有限域 定义定义4.3.2 n阶循环群中，阶循环群中， 每一个每一个n级元素称为级元素称为 n 次次单位原根。单位原根。 由上可知， 在 G(a)循环群中单位原根可以不止一个， 凡是(i， n)=1的ai元素都

48、是G(a) 的单位原根。 下面讨论单位原根的个数。 为此首先定义欧拉函数。 第第4章章 多项式环与有限域多项式环与有限域 定义定义4.3.3 0， 1， 2， ， n-1中与中与n互素的个数称互素的个数称为欧拉函数，为欧拉函数， 记为记为 (n)。 由数论可证明， 若n的标准分解式为 ) 1()() 1()()()(11211121isiiiiiisisppnppppnpppniiiis则 而 代入后得 第第4章章 多项式环与有限域多项式环与有限域 四、 由已知循环群寻找它的全部子群 定理4.3.2 设 G(a) 是由元素a生成的n阶有限循环群， 而H是它的子群。 于是： (1) H仍为有限阶

49、循环群。 它或者是仅由单位元构成的群， 或者是由仅有最小正整数m的元素am所生成； (2) 这种最小正整数m必是n的因子， 且子群的阶为n/m； (3) 对于n的一个因子m(0)， G中必有且仅有一个阶数为n/m的循环子群。 第第4章章 多项式环与有限域多项式环与有限域 证明 (1) 若H仅由单位元素所组成， 则定理已证完， 因为由单位元素所组成的子群仅有一个元素， 故必是有限子群。 另一方面由子群的拉格朗日定理可知， 有限群子群的阶数必是群阶数的因子， 所以子群的元素为有限， 现令m=n/q， 则由于(am)q=a mq =an=e， 因此am生成的子群必是q阶有限循环群， 显然这个m是生成

50、q阶循环群的最小m， q=n/m。 第第4章章 多项式环与有限域多项式环与有限域 (2) 现证 H=G(am)是G(a) 中唯一的q=n/m阶子群。 若还有一个n/m阶子群H， 它由a m 生成， 则由前面证明可知m是生成q=n/m阶循环群的最小正数， 即m=n/q， 因此m=m， am=a m ， H=H。 若用 d(n) 表示正整数n的因子个数， 则由该定理可知， n阶循环群共有 d(n) 个有限循环子群。 对于无限循环群， 可以证明也有类似的结果。 第第4章章 多项式环与有限域多项式环与有限域 4.4 有限域有限域 (Galoias域域) 的乘法结构的乘法结构 一、一、 基本概念基本概念

51、 域中的所有非域中的所有非0元素构成阿贝尔乘群，元素构成阿贝尔乘群， 所有元素构所有元素构成阿贝尔加群。成阿贝尔加群。 若为有限域，若为有限域， 则元素的个数为有限。则元素的个数为有限。 因此，因此， 所有非所有非0元素全体一定构成一个有限乘群，元素全体一定构成一个有限乘群， 群群中每个元素的级为有限，中每个元素的级为有限， 并由定理并由定理4.3.1可知它必由一可知它必由一个元素生成且是循环群。个元素生成且是循环群。 不仅如此，不仅如此， 下面我们将证明下面我们将证明在任何在任何q阶有限域中能找到一个生成元素阶有限域中能找到一个生成元素， 第第4章章 多项式环与有限域多项式环与有限域 它的级

52、为它的级为q-1， 能生成域中所有能生成域中所有q-1个非个非0元素，元素， 从而从而组成一个循环乘群组成一个循环乘群 G()： 1， ， 2， ， q-2 ， q-1 =1。 定义定义4.4.1 域中非域中非0元素所构成的乘法群之阶定义为元素所构成的乘法群之阶定义为域中该元素的级。域中该元素的级。 第第4章章 多项式环与有限域多项式环与有限域 定义定义4.4.2 若若为域为域 GF(q) 中的中的n级元素，级元素， 则称则称为为 n次次单位原根单位原根。 若在若在 GF(q) 中，中， 某一元素某一元素的级为的级为q-1， 则称则称为为本原域元素本原域元素。 由于由于GF(q)中所有中所有q

53、-1个非个非0元素组成一个乘群，元素组成一个乘群， 因因此本原域元素此本原域元素能生成这个乘群，能生成这个乘群， 与循环群中的定义与循环群中的定义类似，类似， 显然有显然有a q-1 =e。 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.4.1 在在 GF(q) 中，中， 每一个非每一个非0元素均满足元素均满足 x q-1 =1， 即都是即都是x q-1 -1=0方程的根。方程的根。 反之，反之， x q-1 -1=0的根必在的根必在 GF(q) 中。中。 证明 由定理4.2.5知， x q-1 -1=0方程至多有q-1个根。 下面证明 GF(q) 中的所有q-1个元素就是该方程的

54、全部根。 xq-x=x(x q-1 -1)=(x-0)(x q-1 -1) 第第4章章 多项式环与有限域多项式环与有限域 因此 GF(q) 中的0元素是xq-x=0方程的一个根。 因为 GF(q) 中的q-1个非0元素组成一个循环乘群， 它由级为q-1的的所有幂次组成： 0=1， ， 2， ， q-2 因为1， ， 2， ， q-2 中的每一个均满足： (i)q-1 =( q-1 )i=1 i=0， 1， 2， ， q-2 第第4章章 多项式环与有限域多项式环与有限域 或 (i)q-1 -1=0 i=0， 1， 2， ， q-2 所以 GF(q) 中的q-1个元素都是x q-1 =0方程的根。

55、 反之， 若是方程x q-1 -1=0的根， 则q-1 =1， 因此必是由 GF(q) 中的本原域元素的幂次生成， 也就是是 GF(q) 中的元素。 第第4章章 多项式环与有限域多项式环与有限域 推论推论4.4.1 由由 GF(q) 中中n级元素级元素生成的循环群生成的循环群 G() ， 一定是一定是xn-1=0方程的根。方程的根。 在上面曾谈到， GF(q) 中的所有q-1个非0元素组成一个循环群。 换言之， q-1个非0元素一定可以由一个级为q-1的本原域元素生成， 下面定理说明了这点。 定理4.4.2 GF(q) 中必有本原域元素存在。 第第4章章 多项式环与有限域多项式环与有限域 二、

56、二、 分圆多项式分圆多项式 设设是是 GF(q) 的的n级元素，级元素， 则由循环群的性质可知，则由循环群的性质可知， G()=1， ， 2， ， n-1 是一个由是一个由生成的循环子生成的循环子群，群， 由定理由定理4.4.1及推论及推论4.4.1可知，可知， xn-1=0方程的全部方程的全部根，根， 就是就是GF(q)内的内的G() 子群的元素。子群的元素。 因而因而 xn-1=(x-0)(x-)(x-2)(x- n-1 )= )(10inix第第4章章 多项式环与有限域多项式环与有限域 定理定理4.4.3 在含有在含有n次单位原根的任意域上，次单位原根的任意域上， 有下有下述因式分解：述

57、因式分解： )(110jnindxx第第4章章 多项式环与有限域多项式环与有限域 定义定义4.4.3 以以 GF(q)中彼此不同的中彼此不同的d级元素为全部根级元素为全部根的首一多项式，的首一多项式， 称为称为 d级分圆多项式级分圆多项式 ， 记为记为Q (d) (x)。 定理定理4.4.4 d级分圆多项式级分圆多项式Q(d) (x)的次数为的次数为(d)。 第第4章章 多项式环与有限域多项式环与有限域 证明 由元素级的性质可知， 若为d级元素， 则i为d级元素的充要条件是 (d， i)=1。 因为Q(d) (x)是由级为d的元素作根的一次因式的乘积作成， 而在G()=， 2， 3， ， d(

58、G()GF(q)集合中， 仅含有(d)个与d互素的元素， 也即仅含有(d)个d级元素， 所以Q(d) (x)是(d) 次多项式。 第第4章章 多项式环与有限域多项式环与有限域 例例4.9 分解分解 GF(2)上的上的x 15 -1多项式。多项式。 x 15 -1共有共有15个根，个根， 由定理由定理4.4.1知，知， GF(16)=GF(2 4)上的所有上的所有15个非个非0元素都是它的根。元素都是它的根。 15的因子有的因子有1， 3， 5， 15， 故在故在GF(2 4)中中 的非的非0元素的级分别为元素的级分别为1， 3， 5， 15级。级。 由式由式(4.4.1)知：知： )()()(

59、)()(1)15()5()3()1(15|)(15xQxQxQxQxQxddd第第4章章 多项式环与有限域多项式环与有限域 Q(1) (x) 是以是以1级元素级元素0=1为根为根 Q(3) (x) 是以是以3级元素级元素5、 10 为根为根 Q(5) (x) 是以是以5级元素级元素3、 6、 9、 12 为根为根 Q(15) (x) 是以是以15级元素级元素、 2、 4、 8、 7、 14 、 13 、 11 为根为根第第4章章 多项式环与有限域多项式环与有限域 所以所以 Q(1) (x)=(x-1) Q(3) (x)=(x-5)(x- 10 ) Q(5) (x)=(x-3)(x-6)(x-9

60、)(x- 12 ) Q(15) (x)=(x-)(x-2)(x-4)(x-8)(x-7) (x- 14 )(x- 13 )(x- 11 ) 故故 )()(1141)(15, 5 , 3 , 115dxxQxiddQ (d) (x)分解成分解成GF(2)？第第4章章 多项式环与有限域多项式环与有限域 定义定义4.4.41) 1(0)(ka 若若a含有平方因子含有平方因子 a不含有平方因子不含有平方因子a=p1p2pka=1 为为Mobius函数，函数， 上式中上式中p1， p2， ， pk为素数。为素数。 第第4章章 多项式环与有限域多项式环与有限域 定理定理4.4.5 )(/|)/(|)()