数论与有限域第六章.ppt

1、第六章 有限域的抽象性质,第一节 有限域的加法结构,一、域的特征 二、有限域F中的元素个数,一、域的特征,设e为有限域F中的乘法单位元。定义F中的序列u0, u1, u2,如下 u0=0, un=un-1+e, 其中n=1, 2,. 则易知nZ，有un=ne，于是在此序列中，m和n，有 um+n=(m+n)e=me+ne=um+un 且 umn=(mn)e=(mn)e2=mene=umun。 由于F是有限域，因而序列u0, u1, u2,中的元素不可能都不相同，故可设存在整数c，使得u0=0, u1, u2, uk+c-1互不相同且uk+c=uk。又uk+c-uk=uc，即uc=ce=0。因而

2、我们找到了一个整数c，使得ce=0。一般地,一、域的特征,定义6.1.1记有限域F的乘法单位元为e，如果存在正整数n，使得ne=0，则称满足此条件的最小正整数n为域F的特征。如果这样的正整数不存在，则称域F的特征为零。 例6.1.1 容易验证由前一章的例5.4.5得到的域GF(8)的特征为 2， 由例5.4.4得到域GF(9)的特征为 3， 而实数域与有理数域的特征则为 0。,一、域的特征,定理6.1.1若F是有限域，则F的特征c必定为素数。 证明：假设相反，设正整数c=ab，其中1ac，1bc，则由上述有限域F中的序列u0, u1, u2,所具有的性质知 uc=uaub。 但uc=0，而ua

3、与ub均不为0，如此与域中无零因子的性质相矛盾，因而c必定为素数。 在以下的叙述中，记有限域的特征为字母p，则易知序列u0, u1, u2,中第一个出现重复的元素是 up=0，进而u0, u1, u2, up-1互不相同。,二、有限域F中的元素个数,定理6.1.2有限域F中的元素个数q必定是某个素数p的幂次，即q=pm。 证明：首先，容易验证域F的子集u0, u1, u2, up-1构成了F的一个子域，记为Fp。 若F=Fp，则q=p，结论得证。 否则设1F-Fp，则a, bFp，在F中都可以对应地找到一个元素a1+b，显然在F中共有p2个元素具有这样的形式，因而若域F中元素的数目q=p2，则

4、定理得证。,二、有限域F中的元素个数,否则在F中选择不具有形式a1+b的元素2，则a, b, cFp，在F中都可以对应地找到一个元素a2+b1+c，显然在F中共有p3个元素具有此形式，因而若域F中元素的数目q=p3，则定理得证。 否则，我们在F中选择不具有形式a2+b1+c的元素3，。 最终，在F中可以选定一组元素1,2,m-1，使得F中的每个元素都有唯一的表达式：=a1+a21+a32+am-1m-1，其中aiFp，i=1, 2, , m-1。由于每个ai有p个可能的取值，因而F中恰有pm个元素。定理得证,二、有限域F中的元素个数,通过定理6.1.2，对有限域F的加法结构我们可以得到如下认识

5、： 有限域F中的元素可以看做是域Fp中元素构成的m元组，且 (a1, a2,am)+(b1,b2,bm)=(a1b1, a2+b2, am+bm) 接下来，我们来研究域F的乘法结构。,第二节 有限域的乘法结构,一、元素的阶 二、本原元 三、最小多项式与本原多项式,一、元素的阶,以下设F为有限域，F*为有限域F中的所有非零元素构成的集合，F*，考察由的各个幂次所构成的序列e, , 2, n,的性质。 首先由域F对乘法运算的封闭性，知i，iF，又F是有限域，因而序列e, , 2, n,中必然会出现重复。 设e, , 2, k+t-1互不相同且k=k+t，则 k=0； 否则若k0，则由k=k+t得到

6、 k-1=k+t-1， 这与e, , 2, k+t-1互不相同相矛盾，进而t=e。 一般地,一、元素的阶,定义6.2.1 记有限域F的乘法单位元为e，则称使得等式t=e成立的最小正整数t，t1，为的阶，记为ord()。 通常，取不同值，的阶相应地也会有不同的取值，并且计算有可能也会很困难。但是，在域F中利用以下结论可以很明确地确定出t，t1，阶元素的个数。,一、元素的阶,定理6.2.1设有限域F具有q个元素，F*，若的阶为t，则t|(q-1)。 证明：由域的定义，F*构成了乘法群，由于的阶为t，即 t=e， 因而e, , 2, t-1构成了F*的子群。拉格朗日定理子群中的元素个数一定会是整个群

7、的元素个数的因子，因而 t|(q-1)。,一、元素的阶,引理6.2.1设F为有限域，若p(x)是Fx中的m次多项式，则在域F中方程p(x)=0至多有m个不同的根。 证明：对m进行数学归纳。 若m=1，此时p(x)为一次多项式，即方程p(x)=0具有形式ax+b=0，显然该方程只有一个根x=-a-1b。 若m2，且方程p(x)=0没有根，则定理得证； 否则，设为方程p(x)=0的根，即 p()=0，以(x-)除以p(x)由带余数除法可以得到 p(x)=q(x)(x-)+r(x)， 其中deg(r(x)deg(x-)，或者r(x)=0，,一、元素的阶,从而r(x)是Fx中的常数多项式，也即域F中的

8、一个元素。由于p()=0，因而 p()=q()(-)+r()=0，即r()=0， 而r(x)是域F中的一个元素，因而 r(x)=0，于是 p(x)=q(x)(x-)， 并且方程p(x)=0的任意一个不等于的根都是方程q(x)=0的根。 但是q(x)的次数为m-1，由归纳假设方程q(x)=0至多有m-1个根，因而方程p(x)=0至多有m个根。,一、元素的阶,例6.2.1设Z8为整数模8的剩余类环，即 定义了模8的加法和乘法运算的集合0,1,2,7。 在这个环中，通过验证我们会发现多项式方程x2-1=0有4个不同的根 x=1,3,5,7。 即我们竟然得到了一个有4个根的二次方程，这似乎与我们给出的

9、引理6.2.1矛盾。但是需要注意的是Z8中有零因子2和4，因而不是域，故并不矛盾。,一、元素的阶,推论6.2.1 若ord()=t，则每个满足方程xt=e的域F中的元素都必定是的幂。 证明：若ord()=t，即t=e，则 (i)t-e=(t)i-e=0， 即t个元素e, , 2, t-1是方程xt-e=0的t个不同的根，而由引理6.2.1该方程不会再有其它的根！即 每个满足方程xt=e的域F中的元素都必定是的幂。 但是正如下面的引理6.2.2所述的，并不是的每个幂次都有阶t。,一、元素的阶,引理6.2.2若ord()=t，则ord(i)=t/gcd(i,t)。 证明：首先，易知0，有s=e当且

10、仅当ord()|s。 其次，设d=gcd(i,t)，则 i(t/d)=t(i/d)=(t)(i/d)=e。因而ord(i)|(t/d)。 另设s=ord(i)，则is=(i)s=e，而ord()=t，因而t|is。由于d=gcd(i,t)，因而存在某整数a和b，使得 ia+tb=d。 于是 ias+tbs=ds。 则由t|is，有t|ds，即(t/d)|s，因而(t/d)|ord(i)。结合ord(i)|(t/d)，就得到 ord(i)=t/d，也即ord(i)=t/gcd(i,t)。,一、元素的阶,例6.2.2设域F中的元素的阶ord()=8，则利用引理6.2.2可以计算i ，i=0, 1,

11、7的阶的结果如下表： 表6-1 域F中各元素阶列表,表6-1 中有： 4个8阶的元素， 2个4阶的元素， 1个2阶的元素， 以及1个1阶的元素；,一、元素的阶,定理6.2.2设t为整数，则在域F中或者没有t阶元素，或者恰有(t)个t阶元素。 证明：若在域F中没有t阶元素，则定理得证。 反之，若ord()=t，正如上面所观察到的每个t阶元素都在集合 1, , 2, t-1中。 但是由引理6.2.2，i的阶为t当且仅当 gcd(t,i)=1。 因而这样的i恰有(t)个。,一、元素的阶,到此，对于有q个元素的有限域F的元素的阶我们有这样的认识： 给定正整数t，若t(q-1)，则在域F中不存在t阶元素

12、； 若t|(q-1)，则在域F中或者没有t阶元素，或者恰有(t)个t阶元素。 接下来我们证明若t确实整除q-1，则在域F中将总是存在有(t)个t阶元素。在给出具体证明之前，再来看另外一个例子。,一、元素的阶,例6.2.3设q=9，则q-1=8，进而t的可能取值为 1，2，4，8。 又对于t的每一个可能取值，t阶元素的个数或者 为0或者为(t)个。 由欧拉函数的性质，计算得到t和(t)的取值如下表：,注：(t)列的和为8，与域F中的非零元素的个数相同。,一、元素的阶,定理6.2.3若n为正整数，则 。 证明：设Sn为有理数集： ，而 Tn为Sn中的既约分数构成的集合，即 Tn中的元素的分母为n，

13、分子与n相对互素，则 |Sn|=n且|Tn|=(n) (例如 且 )。,一、元素的阶,接下来若设集合Sn中的所有分数都已进行了约简，则 集合Sn中的每一个分数的分母d是n的因子， 其分子e是与n相对互素且介于区间1ed的整数。 反之，若d是n的正因子，1ed，且(e,d)=1，则 分数e/d必是集合Sn中某个分数的约简形式。 进而，对于n的所有因子d，Sn将会分解为若干不相交的集合Td的并集， 即 ，进而 。 同时由于|Sn|=n，|Td|=(d)。因而结论得证。,一、元素的阶,例6.2.4计算(35)。 解：按照欧拉函数的定义，可以在1，2，3，35中逐个测试其是否与35相对互素。 然而，由

14、定理6.2.3应有 (1)+(5)+(7)+(35)=35， 同时， (1)=1，(5)=4，(7)=6， 因而 (35)=351-4-6=24。,一、元素的阶,定理6.2.4设F是有q个元素的有限域，t为正整数。若t(q-1)，则域F中不存在t阶元素；若t|(q-1)，则域F中恰有(t)个t阶元素。 证明：只需证明：若t|(q-1)，则域F中恰有(t)个t阶元素。 对于q-1的每个正因子t，记域F中t阶元素的个数为(t)。则由域F中的每个非零元素的阶都必定整除q-1，可以得到 又 ，进而 但是对于所有的t，(t)-(t)0。因而对于q-1的每个正因子t，都有(t)=(t)。,一、元素的阶,推

15、论6.2.2 在每个有限域中，都至少存在一个（事实上恰有(q-1)个）q-1阶元素。因而任意有限域的乘法群都是循环群。,二、本原元,定义6.2.1称有限域F中阶为q-1的元素，即循环群F*=F-0的生成元，为本原元。 例6.2.5给出域F=Z5以及域F=Z7中的本原元。 解：首先由上节的定理6.2.4，域F=Z5中恰有(4)，即2个本原元，而域F=Z7中恰有(6)，也即2个本原元。下面给出具体地寻找过程。 域F=Z5中的元素为0,1,2,3,4，其中2的幂次依次为 20=1，21=2，22=4，23=3，24=1，因而 2的阶为4，而3的阶为4/gcd(4,3)=4， 4的阶为4/gcd(4,

16、2)=2， 因而2与3是域Z5中的本原元。,二、本原元,例6.2.5给出域F=Z5以及域F=Z7中的本原元。 解：域F=Z7中的元素为0,1,2,3,4,5,6，其中2的幂次为 20=1，21=2，22=4，23=1， 因而2以及其各个幂次均不是域Z7中的本原元。 由于1,2,4都不是本原元，下面我们检验3。3的各个幂次依次为 30=1，31=3，32=2，33=6，34=4，35=5，36=1， 因而3的阶为6，而5的阶为6/gcd(6,5)=6，6的阶为6/gcd(6,3)=2， 因而3与5是域Z7中的本原元。,二、本原元,高斯算法： 第一步：设i=1，取域F中的任意一个非零元1，且记or

17、d(1)=t1。 第二步：若ti=q-1，则算法停止：i即为所寻找的本原元；否则转第三步。 第三步：在域F中选一个非i的幂次的非零元，设ord()=s，若s=q-1，则令i+1=，算法停止；否则转第四步。 第四步：寻找ti的一个因子d，s的一个因子e，使得gcd(d,e)=1且de=lcm(ti,s)。设，ti+1= lcm(ti,s)。i值加1，返回第二步。,二、本原元,注意，在这个算法中： 由于ord(i)=ti，方程的所有解都是i的幂次，因而的阶s不会是ti的因子。进而lcm(ti,s)将会是ti的一个倍数，且会严格大于ti。 在第四步中，找到满足条件d|m，e|n，gcd(d,e)=1

18、且de=lcm(m,n)的两个整数m与n是可能的。例如，m=12，n=18时，可以取d=4，e=9。 在第四步中，元素的阶为ti/gcd(ti,ti/d)=d，的阶为s/gcd(s,s/e)=e。于是这两个元素的乘积的阶为de=lcm(ti,s)。因而在第四步中得到的新的元素i+1的阶ti+1恰好是ord(i)的一个倍数，因而这个算法最终必定会终止于一个本原元。,二、本原元,例6.2.6利用多项式f(x)=x3+2x+1构造一个有限域，并找出域中的本原元。 解：这里只给出了构造域的多项式，并未给出构造域所需的欧氏环，因而可以任意选一个欧氏环，只要保证f(x)为此域中的不可约多项式即可。 注意到

19、在F3中f(0)=1，f(1)=f(2)=2，因而该多项式是 F3x中的一个不可约多项式， 以此可以构造一个具有27个元素的有限域F。 域F中的元素都可以看做是三维向量(a,b,c)，其中a,b,cF3=0,1,2。,二、本原元,在域F中注意到 x3x+2(mod x3+2x+1)， x4x2+2x (mod x3+2x+1)， 因而可定义域F中的加法与乘法运算如下： (a1,b1,c1)+(a2,b2,c2)=(a1+a2,b1+b2,c1+c2)。 (a1,b1,c1)(a2,b2,c2) =(a1a2+a2c1+a1c2+b2b1, 2a1a2+a2b1+a1b2+b1c2+b2c1,

20、2a2b1+a1b2+c1c2) 接下来利用高斯算法寻找这个域中的本原元。,二、本原元,首先取1=(0,1,0)=x，为了计算1的阶，先来计算x的各个幂次对f(x)取模的结果 x01 (mod x3+2x+1), x1x (mod x3+2x+1), x2x2 (mod x3+2x+1) x3x+2(mod x3+2x+1)， x4x2+2x (mod x3+2x+1)， x5x3+2x22x2+x+2 (mod x3+2x+1), x62x3+x2+2xx2+x+1 (mod x3+2x+1) x7x3+x2+xx2+2x+2 (mod x3+2x+1), x8x3+2x2+2x2x2+2

21、(mod x3+2x+1),二、本原元,x92x3+2xx+1 (mod x3+2x+1), x10 x2+x (mod x3+2x+1) x11x3+x2x2+x+2 (mod x3+2x+1), x12x3+x2+2xx2+2 (mod x3+2x+1) x13x3+2x2 (mod x3+2x+1), x142x(mod x3+2x+1) x152x2(mod x3+2x+1), x162x32x+1(mod x3+2x+1) x172x2+x (mod x3+2x+1), x182x3+x2x2+2x+1(mod x3+2x+1),二、本原元,x19x3+2x2+x2x2+2x+2 (

22、mod x3+2x+1), x202x3+2x2+2x2x2+x+1 (mod x3+2x+1) x212x3+x2+xx2+1 (mod x3+2x+1), x22x3+x2x+2(mod x3+2x+1) x232x2+2x(mod x3+2x+1), x242x3+2x22x2+2x+1 (mod x3+2x+1) x252x3+2x2+x2x2+1 (mod x3+2x+1), x262x3+x1 (mod x3+2x+1) 因而1的阶为26，即在高斯算法中有t1=26。 由于t1=q-1=26，算法停止；1就是F中的本原元。,二、本原元,例6.2.7利用多项式f(x)=x2-2构造一

23、个有限域，并找出这个域中的本原元。 解：这里只给出了构造域的多项式，并未给出构造域所需的欧氏环，因而需要选择一个欧氏环，并保证f(x)为此域中的不可约多项式。 注意到在F3中f(0)=1，f(1)=f(2)=2，因而 该多项式是F3x中的一个不可约多项式， 以此可以构造一个具有9个元素的有限域F。 域F中的元素都可以看做是二维向量(a,b)，其中a,bF3=0,1,2。,二、本原元,在域F中注意到x22(mod x2-2)，因而可定义域F中的加法与乘法运算如下： (a1,b1)+(a2,b2)=(a1+a2,b1+b2)。 (a1,b1)(a2,b2)=(a1b2+a2b1, b1b2+2a1

24、a2) 接下来利用高斯算法寻找这个域中的本原元。 首先取1=(1,0)=x，为了计算1的阶，先来计算1=(1,0)=x的各个幂次对f(x)取模的结果 x01 (mod x2-2), x1x (mod x2-2), x22 (mod x2-2) x32x (mod x2-2)， x42x21(mod x2-2)，,二、本原元,因而 1=(1,0)=x的阶为4， 即在高斯算法中有t1=4。 由于t1q-1=8， 因而1不是本原元， 接着转至第3步，需要选择 一个不是1的幂次的元素， 例如可以选 =(1,2)=x+2，则 2=(x+2)2x(modx2-2)=(1,0)，,以二维向量表示为 表6-3

25、 1=(1,0)=x各个幂次的向量表示,二、本原元,类似地可以得到 =(1,2)=x+2的各个幂次对f(x)取模的结果的向量表示 因而的阶 s=8=q-1， 则令2=， 算法停止； 2就是F中的本原元。,表6-4 =(1,2)=x+2的各个幂次的向量表示,二、本原元,例6.2.8 在上例中，由于f(x)=x2-2在F5中也没有2的平方根，因而该多项式也是F5x中的一个不可约多项式，由此也可以构造一个具有25个元素的有限域F如下。 首先域F中的元素都可以看做是二维向量(a,b)，其中a,bF5=0,1,2,3,4。 在域F中注意到x22(mod x2-2)，因而可定义域F中的加法与乘法运算如下：

26、 (a1,b1)+(a2,b2)=(a1+a2,b1+b2)。 (a1,b1)+(a2,b2)= (a1b2+a2b1 , b1b2+2a1a2) 接下来利用高斯算法寻找这个域中的本原元。,二、本原元,首先取1=(1,0)=x，计算得到1=(1,0)=x的各个幂次对f(x)取模的结果的向量表示 因而1的阶为8，即在高斯算法中t1=8。由于t1q-1=24，因而1不是本原元，接着转至第3步，需要选择一个不是1的幂次的元素， 例如可以选=(1,1)=x+1，则 2=(x+1)2 2x+3(modx2-2)=(2,3)， 类似地可以得到的各个幂次对f(x)取模的结果的向量表示如下,表6-5 1=(1

27、,0)=x的 各个幂次的向量表示,二、本原元,因而的阶为12，进而 1=(1,0)，=(1,1)， t1=8，s=12， 转到第四步。 由于lcm(8,12)=24，满足条件gcd(d,e)=1且de=lcm(t1,s)的t1=8的因子d，s=12的因子e，只有d=8，e=3，因而 2=18/812/3=14 =1(21+2)=212+21 =2x2+2x2x+4(mod x2-2) 且2的阶为lcm(8,12)=24。因而t2=24，返回第二步，算法停止；2x+4即为F中的本原元。,三、最小多项式与本原多项式,设F是有pm个元素的有限域，则由前面的讨论F可以看做是Fp上的一个m维向量空间。

28、接下来F，考察F中的m+1个元素1, , 2, m。 由于F在Fp上的维数为m，因而这m+1个元素在Fp上必然是线性相关的，即存在不全为零的元素a0, a1, am，使得 a0+a1+a22+amm=0。 即是多项式方程a(x)=a0+a1x+a2x2+amxm=0的根。 当然，也可以满足其它多项式方程，因而可以定义S()为所有这样的多项式构成的集合，即 S()=f(x)Fpx: f()=0。,三、最小多项式与本原多项式,设p(x)为集合S()中次数最低的非零多项式，f(x)为集合S()中的任意多项式。则由带余数除法，可以找到多项式q(x)与r(x)，使得 f(x)=q(x)p(x)+r(x)

29、，deg(r)deg(p) 但是由于f()=p()=0，因而r()=0。这与deg(p)的最小性相矛盾，因而r(x)=0，进而集合S()中的任意多项式f(x)都是p(x)的倍式。 称集合S()中次数最低的这个多项式p(x)为域F中以为根的最小多项式。若要求p(x)是首一多项式，则 这样的p(x)是唯一的，并且是不可约多项式。 这是由于，若p(x)=a(x)b(x)，则由于p()=0，必然会得到a()=0或b()=0，这与deg(p)的最小性相矛盾。,三、最小多项式与本原多项式,定理6.2.5 设F是有pm个元素的有限域，则F，若Fpx中存在唯一的首一多项式p(x)，使得 p()=0， deg(

30、p)m， 若f(x)为Fp(x)中另外一个以为根的多项式，则p(x)|f(x)。 则称p(x)为的相对于F的子域Fp的最小多项式，若为本原元，则称其所对应的最小多项式为本原多项式。,三、最小多项式与本原多项式,例6.2.9计算例6.2.7所给域中某些个元素的最小多项式。 解：考虑元素(1,0)的幂次，这里暂时将(1,0)记为。 首先0=1，若F中的元素就是Fp中的元素，则其最小多项式将总是 x-，因而0=1的最小多项式为x-1。 接下来，考虑自身。由于不是F3中的元素，因而 x-也不是F3中的元素。 然而，二维向量空间F中的3个向量1=(0,1)，=(1,0)，2=(0,2)必定是线性相关的。

31、 进而可以得到一个以为根的二次方程，由于 2-20=2-21=0， 因而的最小多项式为x2-2，即定义域的多项式。,三、最小多项式与本原多项式,接下来计算2的最小多项式，由于=2=(0,2)，因而 其最小多项式为x-2。 接下来计算=3的最小多项式，首先计算得到它的三个幂次如下 0=1=(0,1)，=3=(2,0)，2=6=(0,2)， 由于2=20，因而的最小多项式为 x2-2或者为x2+1。 接下来计算本原元=(1,2)=x+2的最小多项式。首先计算得到它的三个幂次如下 0=1=(0,1)，=(1,2)，2=(x+2)2x(mod x2-2)=(1,0)， 由于2=+0，因而的最小多项式为

32、 x2-x-1或者为x2+2x+2。,三、最小多项式与本原多项式,以下设F是有限域，K是F的有q个元素的子域。 由前面的讨论知可以将F看做是K上的一个向量空间，故 F中的元素的个数是K中的元素个数q的幂次。 同时q应是某个素数p的幂次，即q=pm。 因而存在某整数n，使得|F|=qn=pnm。 F，将定理6.2.5中的素域Fp替换为K，则 可以得到的相对于域K的最小多项式p(x)。 为了得到p(x)的具体表达式，需要引入如下几个引理,三、最小多项式与本原多项式,引理6.2.3 F，则K当且仅当q=。特别地，xK，有方程xq-x=0。 证明：K， 若=0，则q=； 否则设ord()=t，则t|(

33、q-1)，因而 q-1=1，故q=， 即K中的q个元素为方程xq-x=0提供了q个不同的解。 同时该方程也就只有这q个解，而无其它解。,三、最小多项式与本原多项式,引理6.2.4 若p为素数，则对于1kp-1，有 p整除二项式系数 。 证明：由二项式系数的定义有 该分数的分子被p整除，但分母不被p整除。,三、最小多项式与本原多项式,引理6.2.6设1, 2, , t是任意p特征域中的元素，则 k=1,2,3, 证明：首先当t=1时，结论成立。 当t=2时，利用数学归纳法证明 k=1,2,3,。若k=1， 上述等式中的每个二项式系数都是p的倍数，进而在p特征域中这些系数都是0。因而 。,三、最小

34、多项式与本原多项式,若k=2，则 因而当k=2时结论成立。 以此为基础，由数学归纳法知t=2时，等式 k=1,2,3,，成立。 进而，由数学归纳法知结论成立。,三、最小多项式与本原多项式,一般有限域中的最小多项式。 首先若Kx中的多项式p(x)=p0+p0 x+p2x2+pdxd以为根，即 p()=p0+p0+p22+pdd=0，且piF，i=0,1,d 则 (p0+p1+p22+pdd)q=0，即 p0q+p1qq+p2q2q+ pdqdq=0，于是 p0+p1q+p2(q)2+ pd(q)d=0=p(q)。 因而若是p(x)的根，则q也是p(x)的根。利用同样的推导过程，我们会发现, 等等

35、也都是p(x)的根。,三、最小多项式与本原多项式,定义6.2.2 称，q，, 为相对于子域K的共轭根系，并称此共轭根系中的元素个数为的次数，记为deg()。 定理6.2.6 设F是有qn个元素的有限域，则F，若相对于子域K的共轭根系中的元素个数为d，则d|n且d是满足同余式qd1(modt) 的最小正整数，其中t=ord()。同时 t，若t=d+r，且0rd-1，则,三、最小多项式与本原多项式,证明：假设0，则由于相对于子域K的的各共轭根都是有限域F中的元素，因而序列, q, , 中必定会出现重复。 设 为序列, q, , 中最先出现重复的元素，且 ，其中jd，则 因而ord()|qj(qd-

36、j-1)。但ord()|(qn-1)， 即gcd(ord(), qj)=1。因而ord()|(qd-j-1)， 即 ，也即 也是出现了重复的元素，但是最先出现重复的元素。因而j=0，即,三、最小多项式与本原多项式,但F中有qn个元素，因而 因而 。由于 是最先出现重复的元素，因而必定有 gcd(d,n)=d，即d是n的一个因子。 因而的不同共轭根的个数是n的一个因子。 同时，通过前面的讨论，发现d是满足式qd1(mod t) 的最小正整数，其中t=ord()。 综合以上讨论知结论成立。,三、最小多项式与本原多项式,由定理6.2.6相对于子域K的共轭根系中的d个元素, q, , ,必定都是的最小

37、多项式的根。因而若定义多项式 f(x)=(x-)(x-q)(x-) (x-)， 则多项式f(x)必定是的最小多项式的一个因式。 并且 定理6.2.7设有限域F有qn个元素，K是F的一个有q个元素的子域。则F，相对于子域K的最小多项式为 f(x)=(x-)(x-q)(x-) (x-) 其中d=deg()，即相对于子域K的共轭根系中的元素个数。,三、最小多项式与本原多项式,证明：首先相对于子域K的最小多项式 f(x)=(x-)(x-q)(x-) (x-) =adxd+ad-1xd-1+a1x+a0， 进而 f(x)q=(x-)q(x-q)q(x-)q(x-)q =adqxdq+ad-1qxq(d-

38、1)+a1qxq+a0q 又(x-)q=xq+(-1)qq=xq-q，因而 f(x)q=(xq-q)(xq-)(xq-)(xq-)=f(xq),三、最小多项式与本原多项式,但由f(x)的展开式应有 f(xq)=adxdq+ad-1x q(d-1)+a1xq+a0 因而aiq=ai，i=0,1,d-1，即ai，i=0,1,d-1，为域K中的元素。 我们已经找到了一个多项式f(x)，它是的最小多项式的一个因式，且其系数都在子域K中。 进而我们可以得到结论： f(x)就是的相对于子域K的最小多项式。,三、最小多项式与本原多项式,例6.2.10当q=2，n=4时，x4+x+1是F2x中的不可约多项式。利用此多项式可以构造一个具有16个元素