离散数学II课件：7_6有限域

1、7.6 有 限 域,有限域(Galois域),定义. 只有有限个元素的域称为有限域(Galois域)。 设F是一个有限域，则 F的特征不可能是0.否则R0F,与元数有限矛盾。 F的特征为质数p，以RP为其最小子域。 设F为q元域，则F中q-1个非0元素在乘法下作成一个q-1元群,因而都适合方程xq-1=1.由此知， F中q-1个非零元素都是多项式xq-1 -1 的根， F中q个元素都是多项式xq x的根。,定理7.6.1 设F为q元域，F中的q-1个非0元素恰是所有q-1次单位根，而F的所有q个元素恰是多项式xq-x的所有的根。 证明：多项式xq-1-1最多只能有q-1个根。但F的非0元素已经

2、是它的q-1个不同的根，所以F的非0元素恰是xq-1-1的所有的根，因而也就是所有的q-1次单位根。类似地可以说明F的所有元素恰是xq-x的所有的根。 结论：xq-1-1和xq-x均无重根。 例. R5=0,1,2,3,4， q=5，它的所有q-1=4个非0元素恰是所有4次单位根，它的所有5个元素恰是多项式x5-x的所有的根。,结论：特征p必不能整除q-1。 证明： （反证）否则(xq-1-1)=(q-1)xq-2=0, 因而xq-1-1有重根，与定理7.6.1矛盾。 定理7.6.2 F的q-1个非0元素在乘法下作成一 个q-1元循环群，其(q-1)个生成元素恰是 q-1(x)的所有的根。 证

3、明：由定理7.6.1,F包含xq-1-1所有的根，自然 也包含q-1(x)的根，故由定理7.6.1和上节定理 7.5.4(定理7.5.4 设n不是F的特征的倍数,并设 n(x)在F中有根。于是，F中恰有n个n次单位 根，它们在乘法下作成一个n元循环群，其 (n)个生成元素恰是n(x)的所有的根。)， 可知该定理成立。,例. R3=0,1,2上的所有复数a+bi(a,bR3)作成的集合F在复数的加、乘下作成一个域。 F=0+0i,0+1i,0+2i,1+0i,1+1i,1+2i,2+0i,2+1i,2+2i 域的特征p=3，元数q=9。则 F中的q-1=8个非0元素是所有q-1=8次单位根: (

4、1+2i)8= (1+2i)9/(1+2i)=(1+(2i)9) /(1+2i) = (1+2i)/(1+2i)=1 因为x8-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上的一个二次质因式。 8(x)在R3上若可约，则可分为一次质因式或二 次质因式，但0，1，2都不是8(x)的根，因此 8(x)只能分解为两个二次质因式的乘积。用待定系数法， 不妨设 8(x)= x4 + 1=（ x2 +ax+ b ）（ x2 +cx+d ） = x4 + (a+c) x3 + (d+a

5、c+b) x2 + (ad+bc)x+bd 比较系数，解出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上的一个二次质因式 （0，1，2都不是(x) 的根）。,=1+i为(x)在F中的一个根:(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 可见，F中的任意元素可以表为 a0 + a1（ a0，a1R3 ）,引理. 设F是q元有限域，特征为p， 设(x)为q-1(x)在Rpx中的一个n次质因式, 是(x)在F中的一个根。 于是，F中的任意元素可以唯一地表为 a0 + a1 + a22 + + an-1n-1 的形式，其中a0，a1，an-1Rp。 证明：规定Rpx到

7、F的一个映射如下： (x) (),证明,(1)往证是Rpx到F上的映射。 显然,(0)=0。 任取F, 0,于是是q-1次单位根， 因为是(x)的根而()q-1(x)，所以 是q-1(x)的根，由定理7.6.2知，是本原q-1次单 位根，因而=k，从而有 xkRpx,使 (xk)=k=. 所以是Rpx到F上的映射。 (2)往证是Rp到F的同态映射。 (x)+g(x)=()+g()=(x)+(g(x)， (x)g(x)=()g()=(x)(g(x),证明,(3) 设的核为N，则由习题7.2习题4知，N为主理想 ，不妨设为(x)Rpx 。 因是(x)的根,(x)=()=0,所以 (x)在核内，故(

8、x)(x)。 因为(x)在 Rp上不可约，所以(x)或是Rp上非零常 元素或与(x)相通。 若(x)是Rp上非零常元素，则N= cRpx= Rpx,因此，整个多项式环Rpx在映射之下都映成0，而是Rpx到F上的映射，故F=0，与F是域矛盾。因而(x)不是常元素。 可见，(x)与(x)相通，所以，的核 N= (x)Rpx= (x)Rpx,即可以写成(x)Rpx的形式。,证明,因为是Rpx到F上的同态映射，同态核为(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) 证表法唯一。设r(x),s(x)是最多n-1次的Rp上面的多项式， =r()=s()，欲证r(x)=s(x)。因为r()- s()=0，故(r(x)-s(x)= r()- s()=0,即r(x)-s(x)在的核内,因而 (x)r(x)-s(x)。 但次(x)= n次(r(x)-s(x)，故 r(x)-s(x)只能是多项式0。 证毕。 结论：F中元素的个数q = pn。 因 = a0 + a1 + a22 + + an-1

10、n-1 中n个系数每个有p种取法。,定理7.6.3,有限域的元数q必为pn的形式，其中p为其特征。 如果同构的域看作是一样的，则对任意q=pn恰 有一个q元有限域。 证明： q = pn已证。 (1)唯一性。 设F,F都是q元有限域,则它们都包含Rp为其子域。 取q-1(x)在Rp上的一个不可约因式(x),据引理的证 明， 因此，若同构的域看作一样，对任意q=pn最多 只能有一个q元有限域。,证明,(2) 存在性。证对任意q=pn确有q元有限域存在。 取q-1(x)在Rpx中的一个不可约因式(x), 则(x)Rpx是Rpx的极大理想(见7.2习题5)， 所以,由定理6.7.10， 是一个域。在

11、Rp中，p个1相加等于0，所以 在域F中，p个 相加等于 ，因而域F的特 征为p。不妨把 ，仍记为0，1， 用代表包含x的那个剩余类：= 于是,()=( )= = = 0,证明,因此,是(x)在F中的根.今(x)q-1(x)， 故是q-1(x) 在F中的根，而q-1不是p的倍 数，由上节定理7.5.4，域F中恰有xq-1-1的q-1 个不同的根。添上0，我们便得到xq-x的q个 不同的根。 往证这q个元素作成的集合F是一个域。显然， F F 。 任取F, F,则 故- F.,证明,任取F, F, 0,则 故 F 这就证明了确有包含q个元素的域存在。 证毕。 除同构的域外，唯一确定的pn元有限域

12、通常记为GF(pn)。,例. 构造元数为8的有限域,并写出该域的加法和乘法表。 解：由于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次质因式（x）。 (由于0，1都不是7(x)的根，故7(x)无一次质因式。 R2上二次质式只有x2+x+1，用它去除7(x)余数为1，因为： 7(x) =x4（x2+x+1）+x（x2+x+1）+1。 可见， 7(x)无二次质因式，只可能分解为两个三 次质因式的乘积。) 用待定系数法求出 7(x)

13、=（x3+x2+1）（x3+x+1）,无论取（x）=x3+x2+1还是取（x）=x3+x+1， 则R2x/(（x）)= 都是元数是8的有限域， 且是同构的。所以，我们不妨取 （x）=x3+x+1，则 R2x/(（x）)= = = 其中 =0,x3+x+1,x（x3+x+1）,x2（x3+x2+1）,， 其余 元素类推。,(3) 若取= ，则 ()= ， 即是(x)在R2x/(（x）)中的一个根。因此 GF(8)=a0 +a1+a22|a0，a1，a2R2 =0,1,+1,2,2+1,2+,2+1。,定理7.6.4,pm-1(x) 在Rpx中的任意质因式(x)必 是m次多项式。因此，对任意m1，

14、Rp 上有m次质式。 证明：命F=GF（pm）。设次(x)=n。 根据引理的证明，F的元数应是pn。因此， n=m。,引理1,tm-1tn-1，当且仅当mn。t是一个文字或 是一个大于1的整数均可。 证明：设 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， 当t是文字时,次(tr-1) 次(tm-1)， 当t是大于1的整数时，tr-1 tm-1， 所以tm-1不整除tn-1。,定理7.6.5,对任意mn，GF(pn)恰有一个子域GF(pm)， GF(pn)的任意子域必为GF(pm)， mn 。 证明： (1) 存在性。设mn,由引理1,pm-1pn-1。 再由引理1， GF(pn)中包含 的所有根，故包含 的所有根，因而包含 的所有根。如 定理7.6.3证明中所证，这pm个根作成一个域 GF(pm). 故GF(pn) 有一个子域GF(pm)。,证明,(2) 唯一性。任