離散數(shù)學(xué)II課件：7_6有限域

1、7.6 有 限 域,有限域(Galois域),定義. 只有有限個(gè)元素的域稱為有限域(Galois域)。 設(shè)F是一個(gè)有限域，則 F的特征不可能是0.否則R0F,與元數(shù)有限矛盾。 F的特征為質(zhì)數(shù)p，以RP為其最小子域。 設(shè)F為q元域，則F中q-1個(gè)非0元素在乘法下作成一個(gè)q-1元群,因而都適合方程xq-1=1.由此知， F中q-1個(gè)非零元素都是多項(xiàng)式xq-1 -1 的根， F中q個(gè)元素都是多項(xiàng)式xq x的根。,定理7.6.1 設(shè)F為q元域，F(xiàn)中的q-1個(gè)非0元素恰是所有q-1次單位根，而F的所有q個(gè)元素恰是多項(xiàng)式xq-x的所有的根。 證明：多項(xiàng)式xq-1-1最多只能有q-1個(gè)根。但F的非0元素已經(jīng)

2、是它的q-1個(gè)不同的根，所以F的非0元素恰是xq-1-1的所有的根，因而也就是所有的q-1次單位根。類(lèi)似地可以說(shuō)明F的所有元素恰是xq-x的所有的根。 結(jié)論：xq-1-1和xq-x均無(wú)重根。 例. R5=0,1,2,3,4， q=5，它的所有q-1=4個(gè)非0元素恰是所有4次單位根，它的所有5個(gè)元素恰是多項(xiàng)式x5-x的所有的根。,結(jié)論：特征p必不能整除q-1。 證明： （反證）否則(xq-1-1)=(q-1)xq-2=0, 因而xq-1-1有重根，與定理7.6.1矛盾。 定理7.6.2 F的q-1個(gè)非0元素在乘法下作成一 個(gè)q-1元循環(huán)群，其(q-1)個(gè)生成元素恰是 q-1(x)的所有的根。 證

3、明：由定理7.6.1,F包含xq-1-1所有的根，自然 也包含q-1(x)的根，故由定理7.6.1和上節(jié)定理 7.5.4(定理7.5.4 設(shè)n不是F的特征的倍數(shù),并設(shè) n(x)在F中有根。于是，F(xiàn)中恰有n個(gè)n次單位 根，它們?cè)诔朔ㄏ伦鞒梢粋€(gè)n元循環(huán)群，其 (n)個(gè)生成元素恰是n(x)的所有的根。)， 可知該定理成立。,例. R3=0,1,2上的所有復(fù)數(shù)a+bi(a,bR3)作成的集合F在復(fù)數(shù)的加、乘下作成一個(gè)域。 F=0+0i,0+1i,0+2i,1+0i,1+1i,1+2i,2+0i,2+1i,2+2i 域的特征p=3，元數(shù)q=9。則 F中的q-1=8個(gè)非0元素是所有q-1=8次單位根: (

4、1+2i)8= (1+2i)9/(1+2i)=(1+(2i)9) /(1+2i) = (1+2i)/(1+2i)=1 因?yàn)閤8-1 = 8(x) 4(x)2(x)1(x)， x4-1 = 4(x)2(x)1(x)，所以， 8(x)= x4 + 1。,(x) = x2 +x+ 2為 8(x)在R3上的一個(gè)二次質(zhì)因式。 8(x)在R3上若可約，則可分為一次質(zhì)因式或二 次質(zhì)因式，但0，1，2都不是8(x)的根，因此 8(x)只能分解為兩個(gè)二次質(zhì)因式的乘積。用待定系數(shù)法， 不妨設(shè) 8(x)= x4 + 1=（ x2 +ax+ b ）（ x2 +cx+d ） = x4 + (a+c) x3 + (d+a

5、c+b) x2 + (ad+bc)x+bd 比較系數(shù)，解出a=1,b=2,c=2,d=2( a=2,b=2,c=1,d=2) 因此， 8(x)= x4 + 1=( x2 +x+ 2)(x2 +2x+2) 故(x) = x2 +x+ 2為 8(x)在R3上的一個(gè)二次質(zhì)因式 （0，1，2都不是(x) 的根）。,=1+i為(x)在F中的一個(gè)根:(1+i)2+ (1+i) +2=0 , 由定理7.6.2 ，知， 是本原8次單位根，且 F中所有非零元素可以表示為的若干次方： 0=1， 1=1+i， 2=(1+i)2=1+2i+ i2 =2i=2(i+1)+1= 2+1 3=(1+i)3=1+i3 =1-

6、i= 1+2i= 2(i+1) +2= 2+2 4= 3 =(1-i) (1+i) =2 5= 4 =2 (1+i) =2 6= 4 2 =2 (2i) =i= (i+1) + 2=+ 2 7= 6 = i (i+1) = i-1 = i+2= (i+1)+1=+ 1 可見(jiàn)，F(xiàn)中的任意元素可以表為 a0 + a1（ a0，a1R3 ）,引理. 設(shè)F是q元有限域，特征為p， 設(shè)(x)為q-1(x)在Rpx中的一個(gè)n次質(zhì)因式, 是(x)在F中的一個(gè)根。 于是，F(xiàn)中的任意元素可以唯一地表為 a0 + a1 + a22 + + an-1n-1 的形式，其中a0，a1，an-1Rp。 證明：規(guī)定Rpx到

7、F的一個(gè)映射如下： (x) (),證明,(1)往證是Rpx到F上的映射。 顯然,(0)=0。 任取F, 0,于是是q-1次單位根， 因?yàn)槭?x)的根而()q-1(x)，所以 是q-1(x)的根，由定理7.6.2知，是本原q-1次單 位根，因而=k，從而有 xkRpx,使 (xk)=k=. 所以是Rpx到F上的映射。 (2)往證是Rp到F的同態(tài)映射。 (x)+g(x)=()+g()=(x)+(g(x)， (x)g(x)=()g()=(x)(g(x),證明,(3) 設(shè)的核為N，則由習(xí)題7.2習(xí)題4知，N為主理想 ，不妨設(shè)為(x)Rpx 。 因是(x)的根,(x)=()=0,所以 (x)在核內(nèi)，故(

8、x)(x)。 因?yàn)?x)在 Rp上不可約，所以(x)或是Rp上非零常 元素或與(x)相通。 若(x)是Rp上非零常元素，則N= cRpx= Rpx,因此，整個(gè)多項(xiàng)式環(huán)Rpx在映射之下都映成0，而是Rpx到F上的映射，故F=0，與F是域矛盾。因而(x)不是常元素。 可見(jiàn)，(x)與(x)相通，所以，的核 N= (x)Rpx= (x)Rpx,即可以寫(xiě)成(x)Rpx的形式。,證明,因?yàn)槭荝px到F上的同態(tài)映射，同態(tài)核為(x)Rpx，所以 (4) 可表性。任取F,有f(x)Rpx，使得 (f(x)= ,以(x)除(x)： (x)= q(x)(x)+ r(x)， 次r(x)n-1。 故, =(f(x)=

9、() =(q(x)(x)+ r(x)= q()()+ r() = q() 0+ r()=r() 因而 = a0 + a1 + a22 + + an-1n-1 .,證明,(5) 證表法唯一。設(shè)r(x),s(x)是最多n-1次的Rp上面的多項(xiàng)式， =r()=s()，欲證r(x)=s(x)。因?yàn)閞()- s()=0，故(r(x)-s(x)= r()- s()=0,即r(x)-s(x)在的核內(nèi),因而 (x)r(x)-s(x)。 但次(x)= n次(r(x)-s(x)，故 r(x)-s(x)只能是多項(xiàng)式0。 證畢。 結(jié)論：F中元素的個(gè)數(shù)q = pn。 因 = a0 + a1 + a22 + + an-1

10、n-1 中n個(gè)系數(shù)每個(gè)有p種取法。,定理7.6.3,有限域的元數(shù)q必為pn的形式，其中p為其特征。 如果同構(gòu)的域看作是一樣的，則對(duì)任意q=pn恰 有一個(gè)q元有限域。 證明： q = pn已證。 (1)唯一性。 設(shè)F,F都是q元有限域,則它們都包含Rp為其子域。 取q-1(x)在Rp上的一個(gè)不可約因式(x),據(jù)引理的證 明， 因此，若同構(gòu)的域看作一樣，對(duì)任意q=pn最多 只能有一個(gè)q元有限域。,證明,(2) 存在性。證對(duì)任意q=pn確有q元有限域存在。 取q-1(x)在Rpx中的一個(gè)不可約因式(x), 則(x)Rpx是Rpx的極大理想(見(jiàn)7.2習(xí)題5)， 所以,由定理6.7.10， 是一個(gè)域。在

11、Rp中，p個(gè)1相加等于0，所以 在域F中，p個(gè) 相加等于 ，因而域F的特 征為p。不妨把 ，仍記為0，1， 用代表包含x的那個(gè)剩余類(lèi)：= 于是,()=( )= = = 0,證明,因此,是(x)在F中的根.今(x)q-1(x)， 故是q-1(x) 在F中的根，而q-1不是p的倍 數(shù)，由上節(jié)定理7.5.4，域F中恰有xq-1-1的q-1 個(gè)不同的根。添上0，我們便得到xq-x的q個(gè) 不同的根。 往證這q個(gè)元素作成的集合F是一個(gè)域。顯然， F F 。 任取F, F,則 故- F.,證明,任取F, F, 0,則 故 F 這就證明了確有包含q個(gè)元素的域存在。 證畢。 除同構(gòu)的域外，唯一確定的pn元有限域

12、通常記為GF(pn)。,例. 構(gòu)造元數(shù)為8的有限域,并寫(xiě)出該域的加法和乘法表。 解：由于8=23，所以，p=2,m=3。 (1)首先求pm-1(x)，即7(x)。 由x7-1=71，x-1=1，得 7(x)=x6 + x5 + x4 + x3 + x2 + x+1 。 (2) 求7(x)在R2x中的3次質(zhì)因式（x）。 (由于0，1都不是7(x)的根，故7(x)無(wú)一次質(zhì)因式。 R2上二次質(zhì)式只有x2+x+1，用它去除7(x)余數(shù)為1，因?yàn)椋?7(x) =x4（x2+x+1）+x（x2+x+1）+1。 可見(jiàn)， 7(x)無(wú)二次質(zhì)因式，只可能分解為兩個(gè)三 次質(zhì)因式的乘積。) 用待定系數(shù)法求出 7(x)

13、=（x3+x2+1）（x3+x+1）,無(wú)論?。▁）=x3+x2+1還是?。▁）=x3+x+1， 則R2x/(（x）)= 都是元數(shù)是8的有限域， 且是同構(gòu)的。所以，我們不妨取 （x）=x3+x+1，則 R2x/(（x）)= = = 其中 =0,x3+x+1,x（x3+x+1）,x2（x3+x2+1）,， 其余 元素類(lèi)推。,(3) 若取= ，則 ()= ， 即是(x)在R2x/(（x）)中的一個(gè)根。因此 GF(8)=a0 +a1+a22|a0，a1，a2R2 =0,1,+1,2,2+1,2+,2+1。,定理7.6.4,pm-1(x) 在Rpx中的任意質(zhì)因式(x)必 是m次多項(xiàng)式。因此，對(duì)任意m1，

14、Rp 上有m次質(zhì)式。 證明：命F=GF（pm）。設(shè)次(x)=n。 根據(jù)引理的證明，F(xiàn)的元數(shù)應(yīng)是pn。因此， n=m。,引理1,tm-1tn-1，當(dāng)且僅當(dāng)mn。t是一個(gè)文字或 是一個(gè)大于1的整數(shù)均可。 證明：設(shè) n = sm+r， 0rm 于是， tn-1 = tsm+ r- tr + tr-1 =tr (tm-1)(tsm-m + tsm-2m + + 1)+tr-1 若mn，則r=0，tr-1=0。故tm-1tn-1。 若m不整除n，則0rm，因此tr-1非0， 當(dāng)t是文字時(shí),次(tr-1) 次(tm-1)， 當(dāng)t是大于1的整數(shù)時(shí)，tr-1 tm-1， 所以tm-1不整除tn-1。,定理7.6.5,對(duì)任意mn，GF(pn)恰有一個(gè)子域GF(pm)， GF(pn)的任意子域必為GF(pm)， mn 。 證明： (1) 存在性。設(shè)mn,由引理1,pm-1pn-1。 再由引理1， GF(pn)中包含 的所有根，故包含 的所有根，因而包含 的所有根。如 定理7.6.3證明中所證，這pm個(gè)根作成一個(gè)域 GF(pm). 故GF(pn) 有一個(gè)子域GF(pm)。,證明,(2) 唯一性。任