第四章 多項(xiàng)式環(huán)與有限域

1、第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 4.1 4.1 子環(huán)與理想子環(huán)與理想 4.2 4.2 多項(xiàng)式剩余類環(huán)多項(xiàng)式剩余類環(huán) 4.3 4.3 循環(huán)群循環(huán)群 4.4 4.4 有限域有限域(Galoias(Galoias域域) )的乘法結(jié)構(gòu)的乘法結(jié)構(gòu) 4.5 4.5 有限域的加法結(jié)構(gòu)有限域的加法結(jié)構(gòu) 4.6 4.6 有限域的代數(shù)結(jié)構(gòu)與多項(xiàng)式的因式分有限域的代數(shù)結(jié)構(gòu)與多項(xiàng)式的因式分解解 習(xí)題習(xí)題 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 4.1 子子 環(huán)環(huán) 與與 理理 想想 一、一、 子環(huán)子環(huán) 類似于子群，類似于子群， 在環(huán)中也可定義子環(huán)。在環(huán)中

2、也可定義子環(huán)。 定義定義4.1.1 若環(huán)中的子集若環(huán)中的子集S， 關(guān)于關(guān)于R中的代數(shù)運(yùn)算也中的代數(shù)運(yùn)算也構(gòu)成環(huán)，構(gòu)成環(huán)， 則稱則稱S是是R的子環(huán)，的子環(huán)， R為為S的擴(kuò)環(huán)。的擴(kuò)環(huán)。 定理定理4.1.1 非空子集非空子集S是是R的子環(huán)的充要條件是：的子環(huán)的充要條件是： (1) 對(duì)任何兩個(gè)元素對(duì)任何兩個(gè)元素a,bS， 恒有恒有a-bS； (2) 對(duì)任何對(duì)任何a,bS， 恒有恒有abS。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 證明證明 若若S是是R的子環(huán)，的子環(huán)， 則由環(huán)的定義可知，則由環(huán)的定義可知， 條件條件(1)、 (2)顯然成立。顯然成立。 若條件若條件(1)、 (2)成立，成立， 則

3、由定理則由定理2.4.2可知，可知， S對(duì)環(huán)對(duì)環(huán)R中的加法運(yùn)算構(gòu)成可換子群，中的加法運(yùn)算構(gòu)成可換子群， 并且并且S關(guān)于關(guān)于R的乘法封的乘法封閉。閉。 由于由于S是環(huán)中的子集，是環(huán)中的子集， 因此因此R中的乘法結(jié)合律，中的乘法結(jié)合律， 加法和乘法間的分配律在加法和乘法間的分配律在S中自然成中自然成立，立， 由此可知由此可知S是是一個(gè)環(huán)。一個(gè)環(huán)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 例例4.1 全體整數(shù)集合構(gòu)成一個(gè)可換環(huán)。全體整數(shù)集合構(gòu)成一個(gè)可換環(huán)。 以某一整數(shù)以某一整數(shù)m的倍數(shù)全體構(gòu)成其中的一個(gè)子集，的倍數(shù)全體構(gòu)成其中的一個(gè)子集， 該子集就是整數(shù)該子集就是整數(shù)環(huán)中的一個(gè)子環(huán)。環(huán)中的一個(gè)

4、子環(huán)。 如如m=3， 則所有則所有3的倍數(shù)的全體集的倍數(shù)的全體集合合0， 3， 6， 9， 構(gòu)成一個(gè)子環(huán)。構(gòu)成一個(gè)子環(huán)。 一個(gè)環(huán)至少有兩個(gè)子環(huán)，一個(gè)環(huán)至少有兩個(gè)子環(huán)， 一個(gè)是由一個(gè)是由0元素組成，元素組成， 一個(gè)是環(huán)一個(gè)是環(huán)R本身，本身， 稱此兩個(gè)子環(huán)為環(huán)稱此兩個(gè)子環(huán)為環(huán)R的的假子環(huán)假子環(huán)， 其其余的稱為余的稱為真子環(huán)真子環(huán)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 二、二、 理想理想 理想理想是很重要的一類子環(huán)，是很重要的一類子環(huán)， 它在環(huán)中的作用相當(dāng)它在環(huán)中的作用相當(dāng)于正規(guī)子群在群中的作用。于正規(guī)子群在群中的作用。 定義定義4.1.2 設(shè)設(shè)R是交換環(huán)是交換環(huán)， I是是R的非空子集，的

5、非空子集， 若若 (1) 對(duì)任意兩個(gè)元素對(duì)任意兩個(gè)元素a,bI， 恒有恒有a-bI； (2) 對(duì)任意對(duì)任意aI， rR， 恒有恒有ar=raI， 則稱則稱I是是R中的一個(gè)理想。中的一個(gè)理想。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 由此定義可知，由此定義可知， 理想理想其實(shí)就是其實(shí)就是可換環(huán)可換環(huán)中的一個(gè)子環(huán)中的一個(gè)子環(huán)， 該子環(huán)也稱雙邊子環(huán)。該子環(huán)也稱雙邊子環(huán)。u由由(1)可知可知I是一個(gè)阿貝爾加群是一個(gè)阿貝爾加群u由由(2)可知可知I的某些元素都由某一元素的某些元素都由某一元素a的倍數(shù)組成。的倍數(shù)組成。 因因此，此， 若理想中包含了元素若理想中包含了元素a， 則它就包含了則它就包含了

6、a的一切倍的一切倍元。元。 u由于由于I構(gòu)成一個(gè)可換加群，構(gòu)成一個(gè)可換加群， 所以可用它作為一個(gè)正規(guī)子所以可用它作為一個(gè)正規(guī)子群，群， 把把R中的元素進(jìn)行分類劃分陪集中的元素進(jìn)行分類劃分陪集。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 例例4.2 全體整數(shù)全體整數(shù) Z 構(gòu)成一個(gè)可換環(huán)，構(gòu)成一個(gè)可換環(huán)， 某一整數(shù)某一整數(shù)m的的倍數(shù)構(gòu)成一個(gè)理想倍數(shù)構(gòu)成一個(gè)理想Im， 以此理想可把全體整數(shù)以此理想可把全體整數(shù) 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 由正規(guī)子群的理論可知，由正規(guī)子群的理論可知， 這些陪集全體這些陪集全體0 ， 1 ,2 ,3 ,4 構(gòu)成一個(gè)模構(gòu)成一個(gè)模5的阿貝爾加群，的阿貝爾加群， 稱為稱為模模5的剩余類群，的剩余類群， 用用Z (mod 5)表示；表示； 一般情況用一般情況用R (mod I)表示之。表示之。 若若R中任二元素中任二元素a、 b屬于屬于I的同一剩余類，的同一剩余類， 則稱則稱a、 b對(duì)模對(duì)模I同余，同余， 記為記

8、為 ab (mod I)或或 a-b0 (mod I)第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.1.2 設(shè)設(shè)R是是可換環(huán)可換環(huán)， I為為R的一個(gè)的一個(gè)理想理想， 于于是是R模模I構(gòu)成一個(gè)可換環(huán)，構(gòu)成一個(gè)可換環(huán)， 稱它為稱它為環(huán)環(huán)R以理想以理想I為模的剩為模的剩余類環(huán)余類環(huán)M。 證明證明 (1) 對(duì)任意對(duì)任意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構(gòu)成阿貝爾加群。構(gòu)成阿貝爾加群。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 (2)

9、乘法封閉性成立，乘法封閉性成立， 交換律成立。交換律成立。 對(duì)一切元素對(duì)一切元素a， bM， 恒有恒有 ab=ab =ab+IM ab=ab = ba =ba (3) 結(jié)合律成立結(jié)合律成立 (ab)c=(ab )c= (ab)c =a(bc) =a( bc )=a( bc ) 由此可知由此可知M組成一可換環(huán)。組成一可換環(huán)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義 4.1.3 在可換環(huán)在可換環(huán)R中，中， 由一個(gè)元素由一個(gè)元素aR所生所生成的理想成的理想I(a)=ra+narR， nZ稱為環(huán)稱為環(huán)R的一的一個(gè)主理想，個(gè)主理想， 稱元素稱元素a為該為該主理想的生成元主理想的生成元。

10、在例在例4.2中，中， 以某一整數(shù)以某一整數(shù)m的倍數(shù)所構(gòu)成的理想的倍數(shù)所構(gòu)成的理想Im就是一個(gè)主理想，就是一個(gè)主理想， m是生成元。是生成元。 如果如果R是一個(gè)有單位是一個(gè)有單位元素的無(wú)零因子可換環(huán)，元素的無(wú)零因子可換環(huán)， 且且R中的每一理想都是主理中的每一理想都是主理想，想， 則稱該則稱該R為主理想環(huán)。為主理想環(huán)。 例如，例如， 整數(shù)環(huán)整數(shù)環(huán) Z 就是一個(gè)就是一個(gè)主理想環(huán)。主理想環(huán)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 4.2 多項(xiàng)式剩余類環(huán)多項(xiàng)式剩余類環(huán) 一、一、 多項(xiàng)式的基本性質(zhì)多項(xiàng)式的基本性質(zhì) 定義定義4.2.1 含有一個(gè)未定元數(shù)含有一個(gè)未定元數(shù)x的域的域Fp(GF(p)上的

11、上的多項(xiàng)式定義為多項(xiàng)式定義為 f(x)=fnxn+f n-1 x n-1 +f1x+f0 fiFp i=0， 1， 2， ， n 且用且用Fpx(或或GF(p)x)表示系數(shù)取自域表示系數(shù)取自域Fp上上 的一切多項(xiàng)式集合。的一切多項(xiàng)式集合。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 多項(xiàng)式次數(shù)：多項(xiàng)式次數(shù)： 稱系數(shù)不為零的稱系數(shù)不為零的x的最高次數(shù)為多項(xiàng)的最高次數(shù)為多項(xiàng)式式f(x)的次數(shù)，的次數(shù)， 記為記為f(x)(f)或或deg f(x)(deg f)。 由此由此可知，可知， 若若fn0， 則則f(x)=n， 稱稱f(x)為為n次多項(xiàng)式。次多項(xiàng)式。 若若fn=f n-1 =f k-1 =0

12、， fk0,則則f(x)=k， 稱稱f(x)為為k次多項(xiàng)次多項(xiàng)式。式。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 首一多項(xiàng)式首一多項(xiàng)式： 最高次數(shù)的系數(shù)為最高次數(shù)的系數(shù)為1的多項(xiàng)式稱為首的多項(xiàng)式稱為首一多項(xiàng)式。一多項(xiàng)式。 下面定義多項(xiàng)式之間的相等、下面定義多項(xiàng)式之間的相等、 相乘和相加規(guī)則。相乘和相加規(guī)則。 設(shè)設(shè) f(x)=fnxn+f n-1 x n-1 +f1x+f0 fiFp g(x)=gnxn+g n-1 x n-1 +g1x+g0 giFp 若對(duì)所有若對(duì)所有 fi=gi i=0， 1， 2， ， n 則稱則稱f(x)=g(x)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 多項(xiàng)

13、式的相加運(yùn)算為多項(xiàng)式的相加運(yùn)算為 f(x)+g(x) =(fn+gn)xn+(f n-1 +g n-1 )x n-1 +(f1+g1)x+(f0+g0) 多項(xiàng)式多項(xiàng)式f(x)=fnxn+f1x+f0與與g(x)=gmxm+g1x+g0的相乘運(yùn)算為的相乘運(yùn)算為 f(x)g(x)=h n+m x n+m +h n+m-1 x n+m-1 +h1x+h0 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 式中式中 nmijjijijjijinmmmigfmnmigfh, 2, 1, 2 , 1 , 00第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.2.1 按以上定義的多項(xiàng)式運(yùn)算，按以上定義的

14、多項(xiàng)式運(yùn)算， Fpx 構(gòu)成一個(gè)具有單位元素、構(gòu)成一個(gè)具有單位元素、 無(wú)零因子的可換環(huán)。無(wú)零因子的可換環(huán)。 證明證明 (1) Fpx 關(guān)于加法構(gòu)成可換群。關(guān)于加法構(gòu)成可換群。 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 4 交換律和結(jié)合律顯然成立。交換律和結(jié)合律顯然成立。 (2) 乘法封閉性成立。乘法封閉性成立。 乘法單位元是乘法單位元是 f(x)=1。 (3) 無(wú)零因子。無(wú)零因

15、子。 設(shè)設(shè) f(x)0， g(x)0， 令令f、 g分別是分別是f(x)和和g(x)的的最高次數(shù)的系數(shù)，最高次數(shù)的系數(shù)， 即即f0、 g0。 因此因此 fg0 fgFp 因?yàn)橛蛞驗(yàn)橛騀p無(wú)零因子，無(wú)零因子， 而而fg是是 f(x)g(x) 的最高次數(shù)的最高次數(shù)項(xiàng)，項(xiàng)， 且不為且不為0， 故故 f(x)g(x)0 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.2.2 給定任意兩個(gè)多項(xiàng)式給定任意兩個(gè)多項(xiàng)式 f(x)g(x)Fpx ， 一定存在有唯一的多項(xiàng)式一定存在有唯一的多項(xiàng)式 q(x)和和r(x) 使使 f(x)=q(x)g(x)+r(x) 0r(x)g(x) 或或 r(x)=0 該

16、定理的證明與定理該定理的證明與定理2.1.2(歐幾里德除法歐幾里德除法)的證明完的證明完全類似，全類似， 這里不再重復(fù)。這里不再重復(fù)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 二、二、 既約多項(xiàng)式既約多項(xiàng)式 與與 Z 環(huán)上的素?cái)?shù)相對(duì)應(yīng)，環(huán)上的素?cái)?shù)相對(duì)應(yīng)， 在在 Fpx 上有既約多上有既約多項(xiàng)式。項(xiàng)式。 定義定義4.2.2 設(shè)設(shè) f(x) 是次數(shù)大于零的多項(xiàng)式，是次數(shù)大于零的多項(xiàng)式， 若除若除了常數(shù)和常數(shù)與本身的乘積以外，了常數(shù)和常數(shù)與本身的乘積以外， 再不能被域再不能被域Fp上的上的其它多項(xiàng)式除盡，其它多項(xiàng)式除盡， 則稱則稱 f(x) 為域?yàn)橛騀p上的既約多項(xiàng)式。上的既約多項(xiàng)式。 第第4

17、章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 由上述定義可得出：由上述定義可得出： 1 一個(gè)常數(shù)總是多項(xiàng)式的因子。一個(gè)常數(shù)總是多項(xiàng)式的因子。 例如，例如， 實(shí)數(shù)域?qū)崝?shù)域上的多項(xiàng)式上的多項(xiàng)式 3x2+1=3(x2+1/3)， 由此可知由此可知3是是3x2+1多項(xiàng)多項(xiàng)式的一個(gè)因子。式的一個(gè)因子。 2 f(x) 是否既約與討論的域有很大關(guān)系。是否既約與討論的域有很大關(guān)系。 例如，例如， f(x)=x2+1 ， 在實(shí)數(shù)域上在實(shí)數(shù)域上是既約的；是既約的； 但在復(fù)數(shù)域上就但在復(fù)數(shù)域上就可以分解為可以分解為 f(x)=(x+i)(x-i)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 判別判別 f(x)(f0)

18、是否既約的方法是：是否既約的方法是： f(x) 既約的充既約的充要條件是要條件是 f(x) 不能再分解成兩個(gè)次數(shù)低于不能再分解成兩個(gè)次數(shù)低于f(x) 的多項(xiàng)的多項(xiàng)式的乘積。式的乘積。 所以，所以， 不論在哪一域上，不論在哪一域上， 凡是一次首一凡是一次首一多項(xiàng)式都是既約多項(xiàng)式。多項(xiàng)式都是既約多項(xiàng)式。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.2.3 每一個(gè)首一多項(xiàng)式每一個(gè)首一多項(xiàng)式 f(x) 必可分解為首必可分解為首一既約多項(xiàng)式之積，一既約多項(xiàng)式之積， 并且當(dāng)不考慮因式的順序時(shí)，并且當(dāng)不考慮因式的順序時(shí)， 這這種分解是唯一的，種分解是唯一的， 即即 式中，式中， pi(x) 為

19、首一既約多項(xiàng)式，為首一既約多項(xiàng)式， i是某一正整數(shù)，是某一正整數(shù)， i=1， 2， ， s。 ixpxpxpxfi)()()()(2121第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 推論推論4.2.1 d次多項(xiàng)式次多項(xiàng)式 f(x) 不可能有多于不可能有多于d個(gè)的一次因式。個(gè)的一次因式。 定理定理4.2.4 為多項(xiàng)式為多項(xiàng)式 f(x) 之根的充要條件是：之根的充要條件是： (x-)f(x) 證明 由多項(xiàng)式的歐幾里德除法可知 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 反之， 若 (x-)f(x) ， 則 f(x)=q(x)(x-) 因?yàn)?=0， 故是x-的根， 由此 f()=q()(-)=0 也是 f(x) 的根。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.2.5 d次多項(xiàng)式至多有次多項(xiàng)式至多有d個(gè)根。個(gè)根。 證明 假定d次多項(xiàng)式 f(x) 有多于d個(gè)根， 則由定理4.2.3和定理4.2.4可知， f(x) 應(yīng)當(dāng)有多于d個(gè)的一次因式， 這與推論4.2.1相矛盾。 定理4.2.6 若p(x)是f(x)的k重既約因式， 則p(x)必是f(x)的導(dǎo)數(shù)f(x)的k-1重既

21、約因式。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 三、 最大(高)公因式 定義4.2.3 若 (f(x)， g(x)， ， k(x)是同時(shí)除盡多項(xiàng)式f(x)， g(x)， ， k(x)的次數(shù)最高的首一多項(xiàng)式， 則稱(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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 與整數(shù)的最大公約數(shù)相似， 可用同樣的方法證明多項(xiàng)式的最大公因式有如下性質(zhì)： 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 2 由整數(shù)的歐幾里德算法， 同樣有多項(xiàng)式的歐幾里德算法： (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) 該算法將在以后詳細(xì)證明。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 四、 最小(低)公倍式 定義4.2.4 若 f(x)， g(x)是同時(shí)能被g(x)、 f(x)除盡的次數(shù)最低的首一多項(xiàng)式， 則稱f(x)， g(x)是

23、g(x)和f(x)的最小公倍式， 用f(x)， g(x)或LCMf(x)， g(x)表示之。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 與整數(shù)的最小公倍數(shù)完全相似， 多項(xiàng)式的最小公倍式也有如下性質(zhì)： 1 f(x)， g(x)， k(x)多項(xiàng)式集合中， 若兩兩互素， 則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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有

24、限域 由上面的討論可知， 由于Fp上多項(xiàng)式全體與整數(shù)全體均構(gòu)成一可換環(huán)， 因此多項(xiàng)式的理論與整數(shù)的理論是完全平行的。 多項(xiàng)式相當(dāng)于一般的整數(shù)， 既約多項(xiàng)式相當(dāng)于素?cái)?shù)， 而常數(shù)(零次多項(xiàng)式)相當(dāng)于整數(shù)中的1， 它既不是既約多項(xiàng)式也不是可約多項(xiàng)式。 多項(xiàng)式與整數(shù)的這種平行關(guān)系， 在下面討論中還將看到。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 五、五、 多項(xiàng)式剩余類環(huán)與有限域的構(gòu)造多項(xiàng)式剩余類環(huán)與有限域的構(gòu)造 如同整數(shù)的剩余類環(huán)一樣，如同整數(shù)的剩余類環(huán)一樣， 以一個(gè)以一個(gè)Fp上的多項(xiàng)式：上的多項(xiàng)式： f(x)=f0+f1x+fnxn f(x)0 為模的剩余類全體也構(gòu)成一個(gè)環(huán)，為模的剩余類全體也

25、構(gòu)成一個(gè)環(huán)， 稱為稱為多項(xiàng)式剩余類多項(xiàng)式剩余類環(huán)環(huán)。 如同整數(shù)剩余類環(huán)的構(gòu)造，如同整數(shù)剩余類環(huán)的構(gòu)造， 我們首先在我們首先在 FpX上上尋找一個(gè)理想尋找一個(gè)理想， 然后然后以此理想為模以此理想為模對(duì)全體對(duì)全體多項(xiàng)式分類，多項(xiàng)式分類， 就得到一個(gè)剩余類環(huán)。就得到一個(gè)剩余類環(huán)。 理想的尋找理想的尋找第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 例子例子4.4 P107第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 引理引理4.2.1 Fpx上任一多項(xiàng)式上任一多項(xiàng)式f(x)的一切倍式集的一切倍式集合合If(x) 組成一個(gè)理想。組成一個(gè)理想。 證明 設(shè) f(x)=f0+f1x+fnxn f(x)0 要證

26、明 f(x) 的一切倍式集合If(x)是一理想， 只要證明： (1) 對(duì)一切a(x)， b(x)If(x)， 有a(x)-b(x)If(x)。 (2) 對(duì)任意c(x)Fpx， a(x)If(x)有c(x)a(x)If(x)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 現(xiàn)證明如下： (1) 因?yàn)閍(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) 是一個(gè)理想。 第第4章章 多項(xiàng)

27、式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義4.2.5 若若 Fpx中的兩多項(xiàng)式中的兩多項(xiàng)式a(x)、 b(x)被同一被同一多項(xiàng)式多項(xiàng)式f(x) 除時(shí)有相同的除時(shí)有相同的 余式：余式： 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)關(guān)于模關(guān)于模f(x) 同余，同余， 記為記為 a(x)b(x) (mod f(x) 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理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)屬于同一剩余類中， 設(shè)屬于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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 反之， 若 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.2.8 以以 f

29、(x)為模的多項(xiàng)式剩余類全體，為模的多項(xiàng)式剩余類全體， 組成一組成一個(gè)有單位元的可換環(huán)個(gè)有單位元的可換環(huán)Fpx/f(x)。 為了證明此定理， 我們首先規(guī)定兩個(gè)陪集或剩余類之間的運(yùn)算如下。 (1) 加法 a(x) + b(x) =a(x)+b(x) 因?yàn)?a(x) =a(x)+If(x) b(x) =b(x)+If(x) 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 所以 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 example P109 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理 4.2.9 若若n(0)次首一多項(xiàng)式次首一多項(xiàng)式f(x)在域在域GF(p)上既上既約，約， 則由則由f(x)為模所組成的多項(xiàng)式剩余類環(huán)是一個(gè)有為模所組成的多項(xiàng)式剩余類環(huán)是一個(gè)有 pn個(gè)元素的有限域個(gè)元素的有限域GF(pn)。 證明 用 f(x)去除任一多項(xiàng)式， 所得余式r(x)的次數(shù)低于f(x)=n， 因此所有次數(shù)低于n次多項(xiàng)式必處在不同的剩余類中。 所以， 下面只要證明每一個(gè)次數(shù)小于n次的多項(xiàng)式g(x) 都有逆元即可。 注意比較

31、：多項(xiàng)式剩余類環(huán)與有限域的構(gòu)造條件的區(qū) 別第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 六、六、 多項(xiàng)式主理想環(huán)多項(xiàng)式主理想環(huán) 定理4.2.1證明了域Fp上的所有多項(xiàng)式全體 Fpx ， 是一個(gè)有單位元的可換環(huán)， 引理4.2.1說(shuō)明了該多項(xiàng)式環(huán)上理想的構(gòu)造。 下面討論主理想的構(gòu)造。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 引理 4.2.2 多項(xiàng)式環(huán) Fpx 中的一切理想均是主理想。 證明 設(shè) Ifx是Fpx的任一理想。 若Ifx僅由零多項(xiàng)式構(gòu)成， 它顯然是主理想。 若Ifx中含有非零多項(xiàng)式， 則其中必含有一個(gè)次數(shù)最低的多項(xiàng)式f(x)。 設(shè)a(x)是Ifx 中任一多項(xiàng)式， 由歐幾里德除法可知

32、： a(x)=q(x)f(x)+r(x) 0 r(x) f(x) 或 r(x)=0 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 由理想定義可知： r(x)=a(x)-q(x)f(x)Ifx 由于 f(x) 是理想中次數(shù)最低的多項(xiàng)式， 且由r(x)的次數(shù)或者等于0或者小于f(x)。 可知， r(x)的次數(shù)只能等于0， 且由無(wú)0多項(xiàng)式的假設(shè)可知r(x)=0。 因此， a(x)=q(x)f(x)Ifx 。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 引理4.2.2中的 f(x) 為主理想的生成元， 或生成多項(xiàng)式。 當(dāng)假定生成多項(xiàng)式為首一多項(xiàng)式時(shí)， 多項(xiàng)式理想中的生成多項(xiàng)式顯然是唯一的。 由引理4

33、.2.1和引理4.2.2可知， Fpx 不僅是一個(gè)有單位元可換環(huán)， 而且也是一個(gè)主理想環(huán)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理4.2.10 多項(xiàng)式剩余類環(huán) Fpx/f(x)中每一理想皆為主理想， 且該主理想的生成多項(xiàng)式必除盡f(x) 。 證明 該定理前半部分證明完全類似于引理4.2.2的證明， 這里不再重復(fù)。 設(shè)I是 Fpx/f(x)中任一理想， g(x) 是它的生成多項(xiàng)式。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 七、 同構(gòu)與自同構(gòu) 由上面討論看到， 以某一素?cái)?shù)p為模的剩余類， 和以某一Fp上的既約多項(xiàng)式 p(x) 為模的多項(xiàng)式剩余類之間， 有幾乎完全相同的結(jié)構(gòu)和性質(zhì)。

34、 一般， 有時(shí)兩個(gè)集合之間的元素不但有一一對(duì)應(yīng)的關(guān)系， 而且有完全相同的性質(zhì)和結(jié)構(gòu)。例如， Fp上的n-1次多項(xiàng)式與Fp上的n重之間的每個(gè)元素， 均存在一一對(duì)應(yīng)關(guān)系。 例如， GF(2)上的二次多項(xiàng)式與GF(2) 上的三重， 它們?cè)刂g有如下一一對(duì)應(yīng)關(guān)系： 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 二次多項(xiàng)式 三重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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義 4.2.6 設(shè)G=1， a， b

35、， 為乘(加)群， 而G是一個(gè)定義了乘(加)法運(yùn)算的集合(不必封閉)， G中乘(加)法用表示， G中乘(加)法用*表示。 若在G與G間建立了一一對(duì)應(yīng)關(guān)系， 把G中元素1， a， b， 變成G中元素1， a， b， ， 且對(duì)任意a， bG有 (ab)=(a)*(b) 稱群G與集合G為群同構(gòu)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 由此可知， 群同構(gòu)是G與G之間的一種一一對(duì)應(yīng)關(guān)系， 對(duì)任何G中的元素a， 恒有a a， 或(a)=a， abab， 即不僅元素之間有一一對(duì)應(yīng)關(guān)系， 而且運(yùn)算結(jié)果也一一對(duì)應(yīng)。第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理 4.2.11 假定群G與G同構(gòu)， 則G

36、亦為群。 證明： (1) 封閉性成立。 設(shè) a， bG， (a)=a， (b)=b， a， bG。 由定義知， (a b)=(a)*(b)=a*b， 因?yàn)閍 bG， 所以a b的像(a b)=a*b也必在G中， 故a*bG。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 (2) 結(jié)合律成立。 設(shè)a， b， cG， 則 (a*b)*c =(a b)*(c)=(a b) c) =(a (b c) =(a)*(b c)=a*(b*c) (3) 有單位元。 (1)=1即為單位元。 因?yàn)閷?duì)任一aG， 有a*1=(a 1)=(a)=a。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 (4) 有逆元。 對(duì)任

37、一個(gè) aG， 令a-1 =(a-1 )。 所以 a*a-1 =(a)*(a-1 ) = (a a -1 )=(1)=1。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 同群一樣， 在環(huán)和域等代數(shù)系統(tǒng)中也可建立同構(gòu)。 且也可證明若G是環(huán)或是域， 則G也是環(huán)或域； 當(dāng)然在這種情況下， 必須建立兩種運(yùn)算(加和乘)的對(duì)應(yīng)關(guān)系。 若G=G， 則稱為自同構(gòu)， 稱為群G到自身的映射。 因此， 自同構(gòu)是集合自身到自身的映射。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 4.3 循循 環(huán)環(huán) 群群 有限域在編碼理論中起著非常重要的作用。有限域在編碼理論中起著非常重要的作用。 由第二章由第二章可知，可知， 所謂有

38、限域就是域中元素的個(gè)數(shù)是有限的，所謂有限域就是域中元素的個(gè)數(shù)是有限的， 元元素的個(gè)數(shù)稱為域的階，素的個(gè)數(shù)稱為域的階， 若為若為p階有限域，階有限域， 用用 GF(p)或或Fp表示。表示。 而循環(huán)群的概念則是了解有限域的基礎(chǔ)，而循環(huán)群的概念則是了解有限域的基礎(chǔ)， 它在編碼理論中，它在編碼理論中， 特別在循環(huán)碼理論中起關(guān)鍵作用。特別在循環(huán)碼理論中起關(guān)鍵作用。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 一、一、 循環(huán)群的基本概念循環(huán)群的基本概念在定義循環(huán)群以前，在定義循環(huán)群以前， 先看以下例子。先看以下例子。 例例4.6 考慮以下復(fù)數(shù)域上的三次方程?？紤]以下復(fù)數(shù)域上的三次方程。 x3-1=0 它

39、在復(fù)數(shù)域上有它在復(fù)數(shù)域上有3個(gè)根：個(gè)根： 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 顯然，顯然， 若取其中某一根若取其中某一根x1=e (23)i ， 則這則這3個(gè)根可個(gè)根可通過(guò)這一個(gè)根的各次冪表示。通過(guò)這一個(gè)根的各次冪表示。 x0= x01=1 x1= x11=e (23)i x2= x21=e (43)i 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 事實(shí)上，事實(shí)上， 上述上述3個(gè)根個(gè)根x0、 x1、 x2構(gòu)成阿貝爾乘群：構(gòu)成阿貝爾乘群： 單位元

40、為單位元為x0， 封閉性成立，封閉性成立， 且且x1、 x2互為逆元，互為逆元， 交換交換律顯然滿足。律顯然滿足。 像這種群中的所有元素都可由一個(gè)元素像這種群中的所有元素都可由一個(gè)元素的連續(xù)運(yùn)算的連續(xù)運(yùn)算(在乘群為冪次表示在乘群為冪次表示)而產(chǎn)生的群，而產(chǎn)生的群， 稱為循稱為循環(huán)群，環(huán)群， 由此引入循環(huán)群的定義。由此引入循環(huán)群的定義。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義4.3.1 由一個(gè)單獨(dú)元素的一切冪次所構(gòu)成的群由一個(gè)單獨(dú)元素的一切冪次所構(gòu)成的群稱為循環(huán)群，稱為循環(huán)群， 該元素稱為循環(huán)群的生成元。該元素稱為循環(huán)群的生成元。 例例4.7 整數(shù)全體關(guān)于加法構(gòu)成循環(huán)群，整數(shù)全體

41、關(guān)于加法構(gòu)成循環(huán)群， 它的生成元它的生成元 是是1。 例如：例如： 5=1+1+1+1+1， 6=1+1+1+1+1+1， ， 這里所指的元素這里所指的元素1的冪次是指加法運(yùn)算而言。的冪次是指加法運(yùn)算而言。 15= 1+1+1+1+1=5 16= 1+1+1+1+1+1=6 由于整數(shù)群是一個(gè)無(wú)限群，由于整數(shù)群是一個(gè)無(wú)限群， 故這是一個(gè)無(wú)限循環(huán)群。故這是一個(gè)無(wú)限循環(huán)群。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 二、二、 循環(huán)群的構(gòu)造及其性質(zhì)循環(huán)群的構(gòu)造及其性質(zhì) 設(shè)設(shè)a是循環(huán)群中的任一個(gè)元素，是循環(huán)群中的任一個(gè)元素， 考慮考慮a的一切冪的一切冪an， 這時(shí)可能有兩種情況：這時(shí)可能有兩種情況：

42、 (1) a的所有冪次的所有冪次ah(h=0， 1， 2， 3， )均均不相同，不相同， 這時(shí)由這時(shí)由a生成的群生成的群 G(a)=a -2 ， a -1 ， a0， a1， a2中，中， 元素的個(gè)數(shù)無(wú)限，元素的個(gè)數(shù)無(wú)限， 稱為無(wú)限循環(huán)群。稱為無(wú)限循環(huán)群。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 (2) a的某二次冪相同，的某二次冪相同， 也就是存在有整數(shù)也就是存在有整數(shù)h、 k(且且hk)使使ah=ak， 于是有于是有 aha -k =aka -k =e a h-k =e h-k 為正整數(shù)為正整數(shù) 于是，于是， 群群 G(a) 的元素為：的元素為： e， a1， a2， ， a n=h

43、-k =e， a1， 。 群中元素個(gè)數(shù)有限，群中元素個(gè)數(shù)有限， 所以是有限所以是有限循環(huán)群。循環(huán)群。 稱稱an=e的最小正整數(shù)的最小正整數(shù)n為有限循環(huán)群元素為有限循環(huán)群元素a的的級(jí)。級(jí)。 若為無(wú)限循環(huán)群，若為無(wú)限循環(huán)群， 則則a是無(wú)限級(jí)的。是無(wú)限級(jí)的。 在有限循環(huán)在有限循環(huán)群中，群中， 有以下特點(diǎn)：有以下特點(diǎn)： 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 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 這與假設(shè)這與假設(shè)n是使是使a

44、n=e的最小正整數(shù)相矛盾。的最小正整數(shù)相矛盾。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 2 a為為n級(jí)元素，級(jí)元素， 即即an=e， 則則a的一切冪次生成的的一切冪次生成的元素都在元素都在G(a)=a0=e， a1， a2， ， a n-1 中。中。 設(shè)設(shè)m為為任意整數(shù)，任意整數(shù)， 由歐幾里德除法有由歐幾里德除法有 m=qn+r 0rn am=a qn+r =(an)qar=eqar=ear=ar 而而0rn， 所以所以a的一切冪均在的一切冪均在 G(a) 中。中。 3 凡是循環(huán)群必是可換群。凡是循環(huán)群必是可換群。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.3.1 可換群

45、可換群G中的每一元素中的每一元素a皆能生成一個(gè)循皆能生成一個(gè)循環(huán)群，環(huán)群， 它是它是G的子群。的子群。 若若a是無(wú)限級(jí)元素，是無(wú)限級(jí)元素， 則生成的則生成的是無(wú)限循環(huán)群。是無(wú)限循環(huán)群。 如果如果a是有限級(jí)元素，是有限級(jí)元素， 則生成的是有則生成的是有限循環(huán)群，限循環(huán)群， 元素元素a的級(jí)就是有限循環(huán)群的階數(shù)。的級(jí)就是有限循環(huán)群的階數(shù)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 三、三、 有限循環(huán)群中元素級(jí)的性質(zhì)有限循環(huán)群中元素級(jí)的性質(zhì) 1 若若aG是是n級(jí)元素級(jí)元素,則則am=e的充要條件是的充要條件是nm(m為整數(shù)為整數(shù))。 證明 若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的級(jí)相矛盾， 故r=0， 由此m=qn， nm。 反之， 若nm， 則 am=a qn =(an)q=eq=e 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 2 設(shè)設(shè)a， bG， a為為n級(jí)元素，級(jí)元素， b為為m級(jí)元素，級(jí)元素， 且且(n， m)=1， 則則(ab)之級(jí)等于之級(jí)等于nm。 3 若若a為為n級(jí)元素，級(jí)元素， 則則ak元素之級(jí)為元素之級(jí)為 n/(k， n) 。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 推論4.3.1 若a為dk級(jí)元素， 則ak為d級(jí)元素。 證明

47、 a dk =(ak) d=e 推論4.3.2 n階循環(huán)群中， 每個(gè)元素的級(jí)是群階數(shù)n的因子。 此推論直接由性質(zhì)3得到。 由性質(zhì)3可知， 群中每一元素ai的級(jí)為 n/(i， n)， 若(n， i)=1， 則ai元素的級(jí)亦為n， 也就是說(shuō)由ai的冪次亦可生成循環(huán)群G(a) 中的全部元素： (ai) 0=e， ai， a 2i ， ， a i(n-1) 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義4.3.2 n階循環(huán)群中，階循環(huán)群中， 每一個(gè)每一個(gè)n級(jí)元素稱為級(jí)元素稱為 n 次次單位原根。單位原根。 由上可知， 在 G(a)循環(huán)群中單位原根可以不止一個(gè)， 凡是(i， n)=1的ai元素都

48、是G(a) 的單位原根。 下面討論單位原根的個(gè)數(shù)。 為此首先定義歐拉函數(shù)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義4.3.3 0， 1， 2， ， n-1中與中與n互素的個(gè)數(shù)稱互素的個(gè)數(shù)稱為歐拉函數(shù)，為歐拉函數(shù)， 記為記為 (n)。 由數(shù)論可證明， 若n的標(biāo)準(zhǔn)分解式為 ) 1()() 1()()()(11211121isiiiiiisisppnppppnpppniiiis則 而 代入后得 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 四、 由已知循環(huán)群尋找它的全部子群 定理4.3.2 設(shè) G(a) 是由元素a生成的n階有限循環(huán)群， 而H是它的子群。 于是： (1) H仍為有限階

49、循環(huán)群。 它或者是僅由單位元構(gòu)成的群， 或者是由僅有最小正整數(shù)m的元素am所生成； (2) 這種最小正整數(shù)m必是n的因子， 且子群的階為n/m； (3) 對(duì)于n的一個(gè)因子m(0)， G中必有且僅有一個(gè)階數(shù)為n/m的循環(huán)子群。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 證明 (1) 若H僅由單位元素所組成， 則定理已證完， 因?yàn)橛蓡挝辉厮M成的子群僅有一個(gè)元素， 故必是有限子群。 另一方面由子群的拉格朗日定理可知， 有限群子群的階數(shù)必是群階數(shù)的因子， 所以子群的元素為有限， 現(xiàn)令m=n/q， 則由于(am)q=a mq =an=e， 因此am生成的子群必是q階有限循環(huán)群， 顯然這個(gè)m是生成

50、q階循環(huán)群的最小m， q=n/m。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 (2) 現(xiàn)證 H=G(am)是G(a) 中唯一的q=n/m階子群。 若還有一個(gè)n/m階子群H， 它由a m 生成， 則由前面證明可知m是生成q=n/m階循環(huán)群的最小正數(shù)， 即m=n/q， 因此m=m， am=a m ， H=H。 若用 d(n) 表示正整數(shù)n的因子個(gè)數(shù)， 則由該定理可知， n階循環(huán)群共有 d(n) 個(gè)有限循環(huán)子群。 對(duì)于無(wú)限循環(huán)群， 可以證明也有類似的結(jié)果。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 4.4 有限域有限域 (Galoias域域) 的乘法結(jié)構(gòu)的乘法結(jié)構(gòu) 一、一、 基本概念基本概念

51、 域中的所有非域中的所有非0元素構(gòu)成阿貝爾乘群，元素構(gòu)成阿貝爾乘群， 所有元素構(gòu)所有元素構(gòu)成阿貝爾加群。成阿貝爾加群。 若為有限域，若為有限域， 則元素的個(gè)數(shù)為有限。則元素的個(gè)數(shù)為有限。 因此，因此， 所有非所有非0元素全體一定構(gòu)成一個(gè)有限乘群，元素全體一定構(gòu)成一個(gè)有限乘群， 群群中每個(gè)元素的級(jí)為有限，中每個(gè)元素的級(jí)為有限， 并由定理并由定理4.3.1可知它必由一可知它必由一個(gè)元素生成且是循環(huán)群。個(gè)元素生成且是循環(huán)群。 不僅不僅如此，如此， 下面我們將證明下面我們將證明在任何在任何q階有限域中能找到一個(gè)生成元素階有限域中能找到一個(gè)生成元素， 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 它的級(jí)

52、為它的級(jí)為q-1， 能生成域中所有能生成域中所有q-1個(gè)非個(gè)非0元素，元素， 從而從而組成一個(gè)循環(huán)乘群組成一個(gè)循環(huán)乘群 G()： 1， ， 2， ， q-2 ， q-1 =1。 定義定義4.4.1 域中非域中非0元素所構(gòu)成的乘法群之階定義為元素所構(gòu)成的乘法群之階定義為域中該元素的級(jí)。域中該元素的級(jí)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義4.4.2 若若為域?yàn)橛?GF(q) 中的中的n級(jí)元素，級(jí)元素， 則稱則稱為為 n次次單位原根單位原根。 若在若在 GF(q) 中，中， 某一元素某一元素的級(jí)為的級(jí)為q-1， 則稱則稱為為本原域元素本原域元素。 由于由于GF(q)中所有中所有q

53、-1個(gè)非個(gè)非0元素組成一個(gè)乘群，元素組成一個(gè)乘群， 因因此本原域元素此本原域元素能生成這個(gè)乘群，能生成這個(gè)乘群， 與循環(huán)群中的定義與循環(huán)群中的定義類似，類似， 顯然有顯然有a q-1 =e。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.4.1 在在 GF(q) 中，中， 每一個(gè)非每一個(gè)非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個(gè)根。 下面證明 GF(q) 中的所有q-1個(gè)元素就是該方程的

54、全部根。 xq-x=x(x q-1 -1)=(x-0)(x q-1 -1) 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 因此 GF(q) 中的0元素是xq-x=0方程的一個(gè)根。 因?yàn)?GF(q) 中的q-1個(gè)非0元素組成一個(gè)循環(huán)乘群， 它由級(jí)為q-1的的所有冪次組成： 0=1， ， 2， ， q-2 因?yàn)?， ， 2， ， q-2 中的每一個(gè)均滿足： (i)q-1 =( q-1 )i=1 i=0， 1， 2， ， q-2 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 或 (i)q-1 -1=0 i=0， 1， 2， ， q-2 所以 GF(q) 中的q-1個(gè)元素都是x q-1 =0方程的根。

55、 反之， 若是方程x q-1 -1=0的根， 則q-1 =1， 因此必是由 GF(q) 中的本原域元素的冪次生成， 也就是是 GF(q) 中的元素。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 推論推論4.4.1 由由 GF(q) 中中n級(jí)元素級(jí)元素生成的循環(huán)群生成的循環(huán)群 G() ， 一定是一定是xn-1=0方程的根。方程的根。 在上面曾談到， GF(q) 中的所有q-1個(gè)非0元素組成一個(gè)循環(huán)群。 換言之， q-1個(gè)非0元素一定可以由一個(gè)級(jí)為q-1的本原域元素生成， 下面定理說(shuō)明了這點(diǎn)。 定理4.4.2 GF(q) 中必有本原域元素存在。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 二、

56、二、 分圓多項(xiàng)式分圓多項(xiàng)式 設(shè)設(shè)是是 GF(q) 的的n級(jí)元素，級(jí)元素， 則由循環(huán)群的性質(zhì)可知，則由循環(huán)群的性質(zhì)可知， G()=1， ， 2， ， n-1 是一個(gè)由是一個(gè)由生成的循環(huán)子生成的循環(huán)子群，群， 由定理由定理4.4.1及推論及推論4.4.1可知，可知， xn-1=0方程的全部方程的全部根，根， 就是就是GF(q)內(nèi)的內(nèi)的G() 子群的元素。子群的元素。 因而因而 xn-1=(x-0)(x-)(x-2)(x- n-1 )= )(10inix第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.4.3 在含有在含有n次單位原根的任意域上，次單位原根的任意域上， 有下有下述因式分解：述

57、因式分解： )(110jnindxx第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義4.4.3 以以 GF(q)中彼此不同的中彼此不同的d級(jí)元素為全部根級(jí)元素為全部根的首一多項(xiàng)式，的首一多項(xiàng)式， 稱為稱為 d級(jí)分圓多項(xiàng)式級(jí)分圓多項(xiàng)式 ， 記為記為Q (d) (x)。 定理定理4.4.4 d級(jí)分圓多項(xiàng)式級(jí)分圓多項(xiàng)式Q(d) (x)的次數(shù)為的次數(shù)為(d)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 證明 由元素級(jí)的性質(zhì)可知， 若為d級(jí)元素， 則i為d級(jí)元素的充要條件是 (d， i)=1。 因?yàn)镼(d) (x)是由級(jí)為d的元素作根的一次因式的乘積作成， 而在G()=， 2， 3， ， d(

58、G()GF(q)集合中， 僅含有(d)個(gè)與d互素的元素， 也即僅含有(d)個(gè)d級(jí)元素， 所以Q(d) (x)是(d) 次多項(xiàng)式。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 例例4.9 分解分解 GF(2)上的上的x 15 -1多項(xiàng)式。多項(xiàng)式。 x 15 -1共有共有15個(gè)根，個(gè)根， 由定理由定理4.4.1知，知， GF(16)=GF(2 4)上的所有上的所有15個(gè)非個(gè)非0元素都是它的根。元素都是它的根。 15的因子有的因子有1， 3， 5， 15， 故在故在GF(2 4)中中 的非的非0元素的級(jí)分別為元素的級(jí)分別為1， 3， 5， 15級(jí)。級(jí)。 由式由式(4.4.1)知：知： )()()(

59、)()(1)15()5()3()1(15|)(15xQxQxQxQxQxddd第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 Q(1) (x) 是以是以1級(jí)元素級(jí)元素0=1為根為根 Q(3) (x) 是以是以3級(jí)元素級(jí)元素5、 10 為根為根 Q(5) (x) 是以是以5級(jí)元素級(jí)元素3、 6、 9、 12 為根為根 Q(15) (x) 是以是以15級(jí)元素級(jí)元素、 2、 4、 8、 7、 14 、 13 、 11 為根為根第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 所以所以 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章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定義定義4.4.41) 1(0)(ka 若若a含有平方因子含有平方因子 a不含有平方因子不含有平方因子a=p1p2pka=1 為為Mobius函數(shù)，函數(shù)， 上式中上式中p1， p2， ， pk為素?cái)?shù)。為素?cái)?shù)。 第第4章章 多項(xiàng)式環(huán)與有限域多項(xiàng)式環(huán)與有限域 定理定理4.4.5 )(/|)/(|)()