1、第一節(jié)第一節(jié) 有限域的加法有限域的加法(jif)結(jié)構(gòu)結(jié)構(gòu) 一、域的特征一、域的特征(tzhng) 二、有限域二、有限域F中的元素個(gè)數(shù)中的元素個(gè)數(shù) 第1頁/共67頁第一頁，共67頁。一、域的特征一、域的特征(tzhng)設(shè)設(shè)e為有限域?yàn)橛邢抻騀中的乘法單位元。定義中的乘法單位元。定義F中的序列中的序列u0, u1, u2,如下如下u0=0, un=un-1+e, 其中其中n=1, 2,.則易知?jiǎng)t易知nZ，有，有un=ne，于是在此序列中，于是在此序列中，m和和n，有，有um+n=(m+n)e=me+ne=um+un且且umn=(mn)e=(mn)e2=mene=umun。由于由于F是有限域，因而

2、序列是有限域，因而序列u0, u1, u2,中的元素不可能中的元素不可能都不相同都不相同(xin tn)，故可設(shè)存在整數(shù)，故可設(shè)存在整數(shù)c，使得，使得u0=0, u1, u2, uk+c-1互不相同互不相同(xin tn)且且uk+c=uk。又。又uk+c-uk=uc，即，即uc=ce=0。因而我們找到了一個(gè)整數(shù)。因而我們找到了一個(gè)整數(shù)c，使得使得ce=0。一般地。一般地 第2頁/共67頁第二頁，共67頁。一、域的特征一、域的特征(tzhng)定義記有限域定義記有限域F的乘法單位元為的乘法單位元為e，如果存在正整數(shù)，如果存在正整數(shù)n，使得使得ne=0，則稱滿足此條件，則稱滿足此條件(tioji

3、n)的最小正整數(shù)的最小正整數(shù)n為域?yàn)橛騀的特征。如果這樣的正整數(shù)不存在，則稱域的特征。如果這樣的正整數(shù)不存在，則稱域F的的特征為零。特征為零。例例 容易驗(yàn)證由前一章的例得到的域容易驗(yàn)證由前一章的例得到的域GF(8)的特征為的特征為2，由例得到域由例得到域GF(9)的特征為的特征為3，而實(shí)數(shù)域與有理數(shù)域的特征則為而實(shí)數(shù)域與有理數(shù)域的特征則為0。第3頁/共67頁第三頁，共67頁。一、域的特征一、域的特征(tzhng)定理若定理若F是有限域，則是有限域，則F的特征的特征c必定為素?cái)?shù)。必定為素?cái)?shù)。證明：假設(shè)相反，設(shè)正整數(shù)證明：假設(shè)相反，設(shè)正整數(shù)c=ab，其中，其中1ac，1bc，則由上述，則由上述(s

4、hngsh)有限域有限域F中的序列中的序列u0, u1, u2,所具有的性質(zhì)知所具有的性質(zhì)知uc=uaub。但但uc=0，而，而ua與與ub均不為均不為0，如此與域中無零因子的性，如此與域中無零因子的性質(zhì)相矛盾，因而質(zhì)相矛盾，因而c必定為素?cái)?shù)。必定為素?cái)?shù)。在以下的敘述中，記有限域的特征為字母在以下的敘述中，記有限域的特征為字母p，則易知序，則易知序列列u0, u1, u2,中第一個(gè)出現(xiàn)重復(fù)的元素是中第一個(gè)出現(xiàn)重復(fù)的元素是up=0，進(jìn)而，進(jìn)而u0, u1, u2, up-1互不相同?；ゲ幌嗤?。第4頁/共67頁第四頁，共67頁。二、有限二、有限(yuxin)(yuxin)域域F F中的元素個(gè)數(shù)中的

5、元素個(gè)數(shù)定理有限域定理有限域F中的元素個(gè)數(shù)中的元素個(gè)數(shù)q必定是某個(gè)素?cái)?shù)必定是某個(gè)素?cái)?shù)p的冪的冪次，即次，即q=pm。證明：首先，容易證明：首先，容易(rngy)驗(yàn)證域驗(yàn)證域F的子集的子集u0, u1, u2, up-1構(gòu)成了構(gòu)成了F的一個(gè)子域，記為的一個(gè)子域，記為Fp。若若F=Fp，則，則q=p，結(jié)論得證。，結(jié)論得證。否則設(shè)否則設(shè)1F-Fp，則，則a, bFp，在，在F中都可以對(duì)中都可以對(duì)應(yīng)地找到一個(gè)元素應(yīng)地找到一個(gè)元素a1+b，顯然在，顯然在F中共有中共有p2個(gè)元個(gè)元素具有這樣的形式，因而若域素具有這樣的形式，因而若域F中元素的數(shù)目中元素的數(shù)目q=p2，則定理得證。則定理得證。第5頁/共67

6、頁第五頁，共67頁。二、有限二、有限(yuxin)(yuxin)域域F F中的元素個(gè)數(shù)中的元素個(gè)數(shù)否則在否則在F中選擇不具有形式中選擇不具有形式a1+b的元素的元素2，則，則a, b , cF p ， 在， 在 F 中 都 可 以 對(duì) 應(yīng) 地 找 到 一 個(gè) 元 素中 都 可 以 對(duì) 應(yīng) 地 找 到 一 個(gè) 元 素a2+b1+c，顯然在，顯然在F中共中共(zhn n)有有p3個(gè)元個(gè)元素具有此形式，因而若域素具有此形式，因而若域F中元素的數(shù)目中元素的數(shù)目q=p3，則，則定理得證。定理得證。 否則，我們?cè)诜駝t，我們?cè)贔中選擇不具有形式中選擇不具有形式a2+b1+c的元素的元素3，。最終，在最終，在

7、F中可以選定一組元素中可以選定一組元素1,2,m-1，使，使得得 F 中 的 每 個(gè) 元 素中 的 每 個(gè) 元 素 都 有 唯 一 的 表 達(dá) 式 ：都 有 唯 一 的 表 達(dá) 式 ：=a1+a21+a32+am-1m-1，其中，其中aiFp，i=1, 2, , m-1。由于每個(gè)。由于每個(gè)ai有有p個(gè)可能的取值，因個(gè)可能的取值，因而而F中恰有中恰有pm個(gè)元素。定理得證個(gè)元素。定理得證 第6頁/共67頁第六頁，共67頁。二、有限二、有限(yuxin)(yuxin)域域F F中的元素個(gè)數(shù)中的元素個(gè)數(shù)通過定理，對(duì)有限域通過定理，對(duì)有限域F的加法結(jié)構(gòu)我們可以得到如下認(rèn)識(shí)：的加法結(jié)構(gòu)我們可以得到如下認(rèn)識(shí)

8、：有限域有限域F中的元素可以看做是域中的元素可以看做是域Fp中元素構(gòu)成中元素構(gòu)成(guchng)的的m元組，且元組，且(a1, a2,am)+(b1,b2,bm)=(a1b1, a2+b2, am+bm)接下來，我們來研究域接下來，我們來研究域F的乘法結(jié)構(gòu)。的乘法結(jié)構(gòu)。 第7頁/共67頁第七頁，共67頁。第二節(jié)第二節(jié) 有限域的乘法有限域的乘法(chngf)(chngf)結(jié)構(gòu)結(jié)構(gòu) 一、元素一、元素(yun s)的階的階二、本原元二、本原元 三、最小多項(xiàng)式與本原多項(xiàng)式三、最小多項(xiàng)式與本原多項(xiàng)式第8頁/共67頁第八頁，共67頁。一、元素一、元素(yun s)的階的階以下設(shè)以下設(shè)F為有限域，為有限域，

9、F*為有限域?yàn)橛邢抻騀中的所有非零元素構(gòu)中的所有非零元素構(gòu)成的集合，成的集合，F(xiàn)*，考察由，考察由的各個(gè)冪次所構(gòu)成的序的各個(gè)冪次所構(gòu)成的序列列e, , 2, n,的性質(zhì)。的性質(zhì)。 首先由域首先由域F對(duì)乘法運(yùn)算的封閉性，知對(duì)乘法運(yùn)算的封閉性，知i，iF，又又F是有限域，因而序列是有限域，因而序列e, , 2, n,中必然會(huì)中必然會(huì)出現(xiàn)重復(fù)。出現(xiàn)重復(fù)。 設(shè)設(shè)e, , 2, k+t-1互不相同互不相同(xin tn)且且k=k+t，則，則k=0；否則若否則若k0，則由，則由k=k+t得到得到k-1=k+t-1，這與這與e, , 2, k+t-1互不相同互不相同(xin tn)相矛盾，相矛盾，進(jìn)而進(jìn)而

10、t=e。一般地一般地第9頁/共67頁第九頁，共67頁。一、元素一、元素(yun s)的階的階定義定義 記有限域記有限域F的乘法單位元為的乘法單位元為e，則稱使得等式，則稱使得等式t=e成成立的最小正整數(shù)立的最小正整數(shù)t，t1，為，為的階，記為的階，記為ord()。 通常，通常，取不同值，取不同值，的階相應(yīng)地也會(huì)有不同的取值，的階相應(yīng)地也會(huì)有不同的取值，并且計(jì)算并且計(jì)算(j sun)有可能也會(huì)很困難。但是，在域有可能也會(huì)很困難。但是，在域F中中利用以下結(jié)論可以很明確地確定出利用以下結(jié)論可以很明確地確定出t，t1，階元素的個(gè)，階元素的個(gè)數(shù)。數(shù)。第10頁/共67頁第十頁，共67頁。一、元素一、元素(

11、yun s)的階的階定理設(shè)有限域定理設(shè)有限域F具有具有q個(gè)元素，個(gè)元素，F(xiàn)*，若，若的階為的階為t，則則t|(q-1)。證明：由域的定義，證明：由域的定義，F(xiàn)*構(gòu)成了乘法群，由于構(gòu)成了乘法群，由于(yuy)的階為的階為t，即，即t=e，因而因而e, , 2, t-1構(gòu)成了構(gòu)成了F*的子群。拉格朗日定理的子群。拉格朗日定理子群中的元素個(gè)數(shù)一定會(huì)是整個(gè)群的元素個(gè)數(shù)的因子，子群中的元素個(gè)數(shù)一定會(huì)是整個(gè)群的元素個(gè)數(shù)的因子，因而因而t|(q-1)。第11頁/共67頁第十一頁，共67頁。一、元素一、元素(yun s)的階的階引理設(shè)引理設(shè)F為有限域，若為有限域，若p(x)是是Fx中的中的m次多項(xiàng)式，則在域次

12、多項(xiàng)式，則在域F中方程中方程p(x)=0至多有至多有m個(gè)不同的根。個(gè)不同的根。證明：對(duì)證明：對(duì)m進(jìn)行數(shù)學(xué)歸納。進(jìn)行數(shù)學(xué)歸納。若若m=1，此時(shí)，此時(shí)p(x)為一次多項(xiàng)式，即方程為一次多項(xiàng)式，即方程p(x)=0具有形式具有形式ax+b=0，顯然該方程只有一個(gè)根，顯然該方程只有一個(gè)根x=-a-1b。若若m2，且方程，且方程p(x)=0沒有根，則定理得證；沒有根，則定理得證； 否則否則(fuz)，設(shè)，設(shè)為方程為方程p(x)=0的根，即的根，即 p()=0，以，以(x-)除以除以p(x)由帶余數(shù)除法可以得到由帶余數(shù)除法可以得到p(x)=q(x)(x-)+r(x)， 其中其中deg(r(x)deg(x-)

13、，或者，或者r(x)=0， 第12頁/共67頁第十二頁，共67頁。一、元素一、元素(yun s)的階的階從而從而r(x)是是Fx中的常數(shù)多項(xiàng)式，也即域中的常數(shù)多項(xiàng)式，也即域F中的一個(gè)元中的一個(gè)元素。由于素。由于p()=0，因而，因而p()=q()(-)+r()=0，即，即r()=0，而而r(x)是域是域F中的一個(gè)元素，因而中的一個(gè)元素，因而r(x)=0，于是，于是p(x)=q(x)(x-)，并且方程并且方程p(x)=0的任意一個(gè)不等于的任意一個(gè)不等于的根的根都是方程都是方程q(x)=0的根。的根。但是但是q(x)的次數(shù)為的次數(shù)為m-1，由歸納，由歸納(gun)假設(shè)方程假設(shè)方程q(x)=0至多有

14、至多有m-1個(gè)根，因而方程個(gè)根，因而方程p(x)=0至多有至多有m個(gè)個(gè)根。根。 第13頁/共67頁第十三頁，共67頁。一、元素一、元素(yun s)的階的階例設(shè)例設(shè)Z8為整數(shù)模為整數(shù)模8的剩余類環(huán)，即的剩余類環(huán)，即定義了模定義了模8的加法和乘法運(yùn)算的集合的加法和乘法運(yùn)算的集合0,1,2,7。在這個(gè)環(huán)中，通過驗(yàn)證我們會(huì)發(fā)現(xiàn)多項(xiàng)式方程在這個(gè)環(huán)中，通過驗(yàn)證我們會(huì)發(fā)現(xiàn)多項(xiàng)式方程x2-1=0有有4個(gè)不同的根個(gè)不同的根x=1,3,5,7。即我們竟然即我們竟然(jngrn)得到了一個(gè)有得到了一個(gè)有4個(gè)根的二次方程，個(gè)根的二次方程，這似乎與我們給出的引理矛盾。但是需要注意的是這似乎與我們給出的引理矛盾。但是需

15、要注意的是Z8中有零因子中有零因子2和和4，因而不是域，故并不矛盾。，因而不是域，故并不矛盾。第14頁/共67頁第十四頁，共67頁。一、元素一、元素(yun s)的階的階推論推論 若若ord()=t，則每個(gè)滿足方程，則每個(gè)滿足方程xt=e的域的域F中的元素都必中的元素都必定是定是的冪。的冪。證明：若證明：若ord()=t，即，即t=e，則，則(i)t-e=(t)i-e=0，即即t個(gè)元素個(gè)元素e, , 2, t-1是方程是方程xt-e=0的的t個(gè)不同的根，而個(gè)不同的根，而由引理該方程不會(huì)由引理該方程不會(huì)(b hu)再有其它的根！即再有其它的根！即每個(gè)滿足方程每個(gè)滿足方程xt=e的域的域F中的元素

16、都必定是中的元素都必定是的冪。的冪。但是正如下面的引理所述的，并不是但是正如下面的引理所述的，并不是的每個(gè)冪次都有階的每個(gè)冪次都有階t。 第15頁/共67頁第十五頁，共67頁。一、元素一、元素(yun s)的階的階引理若引理若ord()=t，則，則ord(i)=t/gcd(i,t)。證明：首先證明：首先(shuxin)，易知，易知0，有，有s=e當(dāng)且僅當(dāng)且僅當(dāng)當(dāng)ord()|s。其次，設(shè)其次，設(shè)d=gcd(i,t)，則，則i(t/d)=t(i/d)=(t)(i/d)=e。因而。因而ord(i)|(t/d)。另設(shè)另設(shè)s=ord(i)，則，則is=(i)s=e，而，而ord()=t，因而，因而t|i

17、s。由于。由于d=gcd(i,t)，因而存在某整數(shù)，因而存在某整數(shù)a和和b，使得，使得ia+tb=d。于是于是ias+tbs=ds。則由則由t|is，有，有t|ds，即，即(t/d)|s，因而，因而(t/d)|ord(i)。結(jié)合。結(jié)合ord(i)|(t/d)，就得到，就得到ord(i)=t/d，也即，也即ord(i)=t/gcd(i,t)。第16頁/共67頁第十六頁，共67頁。一、元素一、元素(yun s)的階的階例設(shè)域例設(shè)域F中的元素中的元素(yun s)的階的階ord()=8，則利用引理可，則利用引理可以計(jì)算以計(jì)算i ，i=0, 1,7的階的結(jié)果如下表：的階的結(jié)果如下表： 表表6-1 域域

18、F中各元素中各元素(yun s)階列表階列表 igcd(i,8)i081118224318442518624718表表6-1 中有：中有：4個(gè)個(gè)8階的元素階的元素(yun s)，2個(gè)個(gè)4階的元素階的元素(yun s)，1個(gè)個(gè)2階的元素階的元素(yun s)，以及以及1個(gè)個(gè)1階的元素階的元素(yun s)；第17頁/共67頁第十七頁，共67頁。一、元素一、元素(yun s)的階的階定理設(shè)定理設(shè)t為整數(shù)，則在域?yàn)檎麛?shù)，則在域F中或者沒有中或者沒有(mi yu)t階元素，或階元素，或者恰有者恰有(t)個(gè)個(gè)t階元素。階元素。證明：若在域證明：若在域F中沒有中沒有(mi yu)t階元素，則定理得證。階元

19、素，則定理得證。反之，若反之，若ord()=t，正如上面所觀察到的每個(gè)，正如上面所觀察到的每個(gè)t階元素都在階元素都在集合集合1, , 2, t-1中。中。但是由引理，但是由引理，i的階為的階為t當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)gcd(t,i)=1。因而這樣的因而這樣的i恰有恰有(t)個(gè)。個(gè)。第18頁/共67頁第十八頁，共67頁。一、元素一、元素(yun s)的階的階到此，對(duì)于有到此，對(duì)于有q個(gè)元素的有限域個(gè)元素的有限域F的元素的階我們有這樣的的元素的階我們有這樣的認(rèn)識(shí)：認(rèn)識(shí)：給定給定(i dn)正整數(shù)正整數(shù)t，若，若t (q-1)，則在域，則在域F中不存在中不存在t階階元素；元素；若若t|(q-1)，則在域，

20、則在域F中或者沒有中或者沒有t階元素，或者恰有階元素，或者恰有(t)個(gè)個(gè)t階元素。階元素。接下來我們證明若接下來我們證明若t確實(shí)整除確實(shí)整除q-1，則在域，則在域F中將總是存在有中將總是存在有(t)個(gè)個(gè)t階元素。在給出具體證明之前，再來看另外一階元素。在給出具體證明之前，再來看另外一個(gè)例子。個(gè)例子。第19頁/共67頁第十九頁，共67頁。一、元素一、元素(yun s)的階的階例設(shè)例設(shè)q=9，則，則q-1=8，進(jìn)而，進(jìn)而t的可能取值為的可能取值為1，2，4，8。又對(duì)于又對(duì)于t的每一個(gè)可能取值，的每一個(gè)可能取值，t階元素的個(gè)數(shù)或者階元素的個(gè)數(shù)或者(huzh)為為0或者或者(huzh)為為(t)個(gè)。個(gè)

21、。由歐拉函數(shù)的性質(zhì)，計(jì)算得到由歐拉函數(shù)的性質(zhì)，計(jì)算得到t和和(t)的取值如下表：的取值如下表：t(t)11214284注：注：(t)列的和為列的和為8，與域與域F中的非零元中的非零元素素(yun s)的個(gè)數(shù)的個(gè)數(shù)相同。相同。 第20頁/共67頁第二十頁，共67頁。一、元素一、元素(yun s)的階的階定理若定理若n為正整數(shù)，則為正整數(shù)，則 。證明證明(zhngmng)：設(shè)：設(shè)Sn為有理數(shù)集：為有理數(shù)集： ，而而Tn為為Sn中的既約分?jǐn)?shù)構(gòu)成的集合，即中的既約分?jǐn)?shù)構(gòu)成的集合，即Tn中的元素的分母為中的元素的分母為n，分子與，分子與n相對(duì)互素，則相對(duì)互素，則|Sn|=n且且|Tn|=(n) (例如例

22、如 且且 )。 ndnd|)( ,2,1nnnnSn 86,82,818 S878583,818， T第21頁/共67頁第二十一頁，共67頁。一、元素一、元素(yun s)的階的階接下來若設(shè)集合接下來若設(shè)集合Sn中的所有分?jǐn)?shù)都已進(jìn)行了約簡(jiǎn)，則中的所有分?jǐn)?shù)都已進(jìn)行了約簡(jiǎn)，則集合集合Sn中的每一個(gè)分?jǐn)?shù)的分母中的每一個(gè)分?jǐn)?shù)的分母d是是n的因子，的因子，其分子其分子e是與是與n相對(duì)互素且介于區(qū)間相對(duì)互素且介于區(qū)間1ed的整數(shù)。的整數(shù)。反之，若反之，若d是是n的正因子，的正因子，1ed，且，且(e,d)=1，則，則分?jǐn)?shù)分?jǐn)?shù)e/d必是集合必是集合Sn中某個(gè)分?jǐn)?shù)的約簡(jiǎn)形式。中某個(gè)分?jǐn)?shù)的約簡(jiǎn)形式。進(jìn)而，對(duì)于進(jìn)

23、而，對(duì)于n的所有因子的所有因子d，Sn將會(huì)分解為若干不相交將會(huì)分解為若干不相交的集合的集合Td的并集，的并集，即即 ，進(jìn)而，進(jìn)而 。同時(shí)同時(shí)(tngsh)由于由于|Sn|=n，|Td|=(d)。因而結(jié)論得證。因而結(jié)論得證。 nddnTS| nddnTS|第22頁/共67頁第二十二頁，共67頁。一、元素一、元素(yun s)的階的階例計(jì)算例計(jì)算(35)。解：按照歐拉函數(shù)的定義，可以在解：按照歐拉函數(shù)的定義，可以在1，2，3，35中中逐個(gè)測(cè)試其是否與逐個(gè)測(cè)試其是否與35相對(duì)互素。相對(duì)互素。然而，由定理然而，由定理(dngl)應(yīng)有應(yīng)有(1)+(5)+(7)+(35)=35，同時(shí)，同時(shí)，(1)=1，(

24、5)=4，(7)=6，因而因而(35)=35-1-4-6=24。 第23頁/共67頁第二十三頁，共67頁。一、元素一、元素(yun s)的階的階定理設(shè)定理設(shè)F是有是有q個(gè)元素的有限域，個(gè)元素的有限域，t為正整數(shù)。若為正整數(shù)。若t (q-1)，則域，則域F中不存在中不存在t階元素；若階元素；若t|(q-1)，則域，則域F中恰有中恰有(t)個(gè)個(gè)t階元素。階元素。證明：只需證明：若證明：只需證明：若t|(q-1)，則域，則域F中恰有中恰有(t)個(gè)個(gè)t階元素。階元素。對(duì)于對(duì)于q-1的每個(gè)正因子的每個(gè)正因子t，記域，記域F中中t階元素的個(gè)數(shù)為階元素的個(gè)數(shù)為(t)。則由域。則由域F中的每個(gè)非零元素的階都必

25、定整除中的每個(gè)非零元素的階都必定整除q-1，可以得到，可以得到又又 ，進(jìn)而，進(jìn)而(jn r)但是對(duì)于所有的但是對(duì)于所有的t，(t)-(t)0。因而對(duì)于。因而對(duì)于q-1的每個(gè)正因子的每個(gè)正因子t，都有都有(t)=(t)。 1)()1( | qtqt 1|0)()(qttt 1|1)(qtqt 第24頁/共67頁第二十四頁，共67頁。一、元素一、元素(yun s)的階的階推論在每個(gè)有限域中，都至少存在一個(gè)推論在每個(gè)有限域中，都至少存在一個(gè)(y )（事實(shí)上恰有（事實(shí)上恰有(q-1)個(gè)）個(gè)）q-1階元素。階元素。因而任意有限域的乘法群都是循環(huán)群。因而任意有限域的乘法群都是循環(huán)群。 第25頁/共67頁第

26、二十五頁，共67頁。二、本原二、本原(bnyun)元元 定義稱有限域定義稱有限域F中階為中階為q-1的元素，即循環(huán)群的元素，即循環(huán)群F*=F-0的生成元，為本原元。的生成元，為本原元。例給出域例給出域F=Z5以及域以及域F=Z7中的本原元。中的本原元。解：首先由上節(jié)的定理，域解：首先由上節(jié)的定理，域F=Z5中恰有中恰有(4)，即，即2個(gè)個(gè)本原元，而域本原元，而域F=Z7中恰有中恰有(6)，也即，也即2個(gè)本原元。個(gè)本原元。下面給出具體地尋找過程。下面給出具體地尋找過程。域域F=Z5中的元素為中的元素為0,1,2,3,4，其中，其中2的冪次依次的冪次依次(yc)為為20=1，21=2，22=4，2

27、3=3，24=1，因而，因而2的階為的階為4，而，而3的階為的階為4/gcd(4,3)=4，4的階為的階為4/gcd(4,2)=2，因而因而2與與3是域是域Z5中的本原元。中的本原元。第26頁/共67頁第二十六頁，共67頁。二、本原二、本原(bnyun)元元 例給出域例給出域F=Z5以及以及(yj)域域F=Z7中的本原元。中的本原元。解：域解：域F=Z7中的元素為中的元素為0,1,2,3,4,5,6，其中，其中2的冪次的冪次為為20=1，21=2，22=4，23=1，因而因而2以及以及(yj)其各個(gè)冪次均不是域其各個(gè)冪次均不是域Z7中的本原元。中的本原元。由于由于1,2,4都不是本原元，下面我

28、們檢驗(yàn)都不是本原元，下面我們檢驗(yàn)3。3的各個(gè)的各個(gè)冪次依次為冪次依次為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中的本原元。中的本原元。第27頁/共67頁第二十七頁，共67頁。二、本原二、本原(bnyun)元元 高斯算法：高斯算法：第一步：設(shè)第一步：設(shè)i=1，取域，取域F中的任意中的任意(rny)一個(gè)非零元一個(gè)非零元1，且記且記ord(1)=t1。第二步：若第二步：若ti=q-1，則算法停止：，則算法停止：i即為所尋找的本即為所

29、尋找的本原元；否則轉(zhuǎn)第三步。原元；否則轉(zhuǎn)第三步。第三步：在域第三步：在域F中選一個(gè)非中選一個(gè)非i的冪次的非零元的冪次的非零元，設(shè)，設(shè)ord()=s，若，若s=q-1，則令，則令i+1=，算法停止；否，算法停止；否則轉(zhuǎn)第四步。則轉(zhuǎn)第四步。第四步：尋找第四步：尋找ti的一個(gè)因子的一個(gè)因子d，s的一個(gè)因子的一個(gè)因子e，使得，使得gcd(d,e)=1且且de=lcm(ti,s)。設(shè)，。設(shè)，ti+1= lcm(ti,s)。i值加值加1，返回第二步。，返回第二步。第28頁/共67頁第二十八頁，共67頁。二、本原二、本原(bnyun)元元 注意，在這個(gè)算法中：注意，在這個(gè)算法中：由于由于ord(i)=ti，

30、方程的所有解都是，方程的所有解都是i的冪次，因而的冪次，因而的階的階s不會(huì)是不會(huì)是ti的因子。進(jìn)而的因子。進(jìn)而lcm(ti,s)將會(huì)是將會(huì)是ti的一個(gè)倍數(shù)，的一個(gè)倍數(shù)，且會(huì)嚴(yán)格大于且會(huì)嚴(yán)格大于ti。在第四步中，找到滿足條件在第四步中，找到滿足條件d|m，e|n，gcd(d,e)=1且且de=lcm(m,n)的兩個(gè)的兩個(gè)(lin )整數(shù)整數(shù)m與與n是可能的。例是可能的。例如，如，m=12，n=18時(shí)，可以取時(shí)，可以取d=4，e=9。在第四步中，元素的階為在第四步中，元素的階為ti/gcd(ti,ti/d)=d，的階為，的階為s/gcd(s,s/e)=e。于是這兩個(gè)。于是這兩個(gè)(lin )元素的乘

31、積的階元素的乘積的階為為de=lcm(ti,s)。因而在第四步中得到的新的元素。因而在第四步中得到的新的元素i+1的階的階ti+1恰好是恰好是ord(i)的一個(gè)倍數(shù)，因而這個(gè)算法最的一個(gè)倍數(shù)，因而這個(gè)算法最終必定會(huì)終止于一個(gè)本原元。終必定會(huì)終止于一個(gè)本原元。第29頁/共67頁第二十九頁，共67頁。二、本原二、本原(bnyun)元元 例利用多項(xiàng)式例利用多項(xiàng)式f(x)=x3+2x+1構(gòu)造一個(gè)有限域，并找出域構(gòu)造一個(gè)有限域，并找出域中的本原元。中的本原元。解：這里只給出了構(gòu)造域的多項(xiàng)式，并未給出構(gòu)造域所解：這里只給出了構(gòu)造域的多項(xiàng)式，并未給出構(gòu)造域所需的歐氏環(huán)，因而可以任意選一個(gè)歐氏環(huán)，只要需的歐氏

32、環(huán)，因而可以任意選一個(gè)歐氏環(huán)，只要(zhyo)保證保證f(x)為此域中的不可約多項(xiàng)式即可。為此域中的不可約多項(xiàng)式即可。 注意到在注意到在F3中中f(0)=1，f(1)=f(2)=2，因而該多項(xiàng)式是，因而該多項(xiàng)式是F3x中的一個(gè)不可約多項(xiàng)式，中的一個(gè)不可約多項(xiàng)式， 以此可以構(gòu)造一個(gè)具有以此可以構(gòu)造一個(gè)具有27個(gè)元素的有限域個(gè)元素的有限域F。 域域F中的元素都可以看做是三維向量中的元素都可以看做是三維向量(a,b,c)，其中，其中a,b,cF3=0,1,2。 第30頁/共67頁第三十頁，共67頁。二、本原二、本原(bnyun)元元 在域在域F中注意到中注意到x3x+2(mod x3+2x+1)，x

33、4x2+2x (mod x3+2x+1)，因而可定義域因而可定義域F中的加法與乘法運(yùn)算如下：中的加法與乘法運(yùn)算如下：(a1,b1,c1)+(a2,b2,c2)=(a1+a2,b1+b2,c1+c2)。(a1,b1,c1)(a2,b2,c2)= ( a 1 a 2 + a 2 c 1 + a 1 c 2 + b 2 b 1 , 2a1a2+a2b1+a1b2+b1c2+b2c1, 2a2b1+a1b2+c1c2)接下來利用高斯算法接下來利用高斯算法(sun f)尋找這個(gè)域中的本原元。尋找這個(gè)域中的本原元。第31頁/共67頁第三十一頁，共67頁。二、本原二、本原(bnyun)元元 首先取首先取1=

34、(0,1,0)=x，為了計(jì)算，為了計(jì)算1的階，先來計(jì)算的階，先來計(jì)算x的的各個(gè)各個(gè)(gg)冪次對(duì)冪次對(duì)f(x)取模的結(jié)果取模的結(jié)果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 (mod x3+2x+1)第32頁/共67頁第三十二頁

35、，共67頁。二、本原二、本原(bnyun)元元 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)第33頁/共67頁第三十三頁，共67頁。二、本原二、本原

36、(bnyun)元元 x19x3+2x2+x2x2+2x+2 (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，算法停

37、止；，算法停止；1就是就是(jish)F中的本原元。中的本原元。第34頁/共67頁第三十四頁，共67頁。二、本原二、本原(bnyun)元元 例利用多項(xiàng)式例利用多項(xiàng)式f(x)=x2-2構(gòu)造一個(gè)有限域，并找出這個(gè)域中構(gòu)造一個(gè)有限域，并找出這個(gè)域中的本原元。的本原元。解：這里只給出了構(gòu)造域的多項(xiàng)式，并未給出構(gòu)造域所需解：這里只給出了構(gòu)造域的多項(xiàng)式，并未給出構(gòu)造域所需的歐氏環(huán)，因而需要選擇一個(gè)歐氏環(huán)，并保證的歐氏環(huán)，因而需要選擇一個(gè)歐氏環(huán)，并保證f(x)為此為此域中的不可約多項(xiàng)式。域中的不可約多項(xiàng)式。 注意到在注意到在F3中中f(0)=1，f(1)=f(2)=2，因而，因而該多項(xiàng)式是該多項(xiàng)式是F3x中

38、的一個(gè)不可約多項(xiàng)式，中的一個(gè)不可約多項(xiàng)式， 以此可以以此可以(ky)構(gòu)造一個(gè)具有構(gòu)造一個(gè)具有9個(gè)元素的有限域個(gè)元素的有限域F。域域F中的元素都可以中的元素都可以(ky)看做是二維向量看做是二維向量(a,b)，其中，其中a,bF3=0,1,2。第35頁/共67頁第三十五頁，共67頁。二、本原二、本原(bnyun)元元 在域在域F中注意到中注意到x22(mod x2-2)，因而可定義域，因而可定義域F中的中的加法與乘法運(yùn)算如下：加法與乘法運(yùn)算如下：(a1,b1)+(a2,b2)=(a1+a2,b1+b2)。(a1,b1)(a2,b2)=(a1b2+a2b1, b1b2+2a1a2)接下來利用接下來

39、利用(lyng)高斯算法尋找這個(gè)域中的本原元。高斯算法尋找這個(gè)域中的本原元。首先取首先取1=(1,0)=x，為了計(jì)算，為了計(jì)算1的階，先來計(jì)算的階，先來計(jì)算1=(1,0)=x的各個(gè)冪次對(duì)的各個(gè)冪次對(duì)f(x)取模的結(jié)果取模的結(jié)果x01 (mod x2-2), x1x (mod x2-2), x22 (mod x2-2)x32x (mod x2-2)，x42x21(mod x2-2)，第36頁/共67頁第三十六頁，共67頁。二、本原二、本原(bnyun)元元 因而因而1=(1,0)=x的階為的階為4，即在高斯算法中有即在高斯算法中有t1=4。由于由于t1q-1=8，因而因而1不是本原元，不是本原元

40、，接著轉(zhuǎn)至第接著轉(zhuǎn)至第3步，需要選擇步，需要選擇一個(gè)不是一個(gè)不是1的冪次的元素的冪次的元素，例如例如(lr)可以選可以選=(1,2)=x+2，則，則2=(x+2)2x(modx2-2)=(1,0)， 以二維向量表示以二維向量表示(biosh)為為表表6-3 1=(1,0)=x各個(gè)冪各個(gè)冪次的向量表示次的向量表示(biosh) i1i0(0,1)1(1,0)2(0,2)3(2,0)4(0,1)第37頁/共67頁第三十七頁，共67頁。二、本原二、本原(bnyun)元元 類似地可以得到類似地可以得到=(1,2)=x+2的各個(gè)冪次的各個(gè)冪次對(duì)對(duì)f(x)取模的結(jié)果的取模的結(jié)果的向量表示向量表示因而因而的

41、階的階s=8=q-1，則令則令2=，算法算法(sun f)停止；停止；2就是就是F中的本原元。中的本原元。ii0(0,1)1(1,2)2(1,0)3(2,2)4(0,2)5(2,1)6(2,0)7(1,1)8(0,1)表表6-4 =(1,2)=x+2的各個(gè)的各個(gè)冪次的向量冪次的向量(xingling)表表示示第38頁/共67頁第三十八頁，共67頁。二、本原二、本原(bnyun)元元 例在上例中，由于例在上例中，由于f(x)=x2-2在在F5中也沒有中也沒有2的平方根，的平方根，因而該多項(xiàng)式也是因而該多項(xiàng)式也是F5x中的一個(gè)不可約多項(xiàng)式，中的一個(gè)不可約多項(xiàng)式，由此也可以構(gòu)造一個(gè)具有由此也可以構(gòu)造

42、一個(gè)具有25個(gè)元素的有限域個(gè)元素的有限域F如下。如下。首先域首先域F中的元素都可以看做是二維向量中的元素都可以看做是二維向量(a,b)，其中，其中a,bF5=0,1,2,3,4。在域在域F中注意中注意(zh y)到到x22(mod x2-2)，因而可定義，因而可定義域域F中的加法與乘法運(yùn)算如下：中的加法與乘法運(yùn)算如下：(a1,b1)+(a2,b2)=(a1+a2,b1+b2)。(a1,b1)+(a2,b2)= (a1b2+a2b1 , b1b2+2a1a2)接下來利用高斯算法尋找這個(gè)域中的本原元。接下來利用高斯算法尋找這個(gè)域中的本原元。第39頁/共67頁第三十九頁，共67頁。二、本原二、本原(

43、bnyun)元元 首先取首先取1=(1,0)=x，計(jì)算，計(jì)算(j sun)得到得到1=(1,0)=x的各個(gè)冪的各個(gè)冪次對(duì)次對(duì)f(x)取模的結(jié)果的向量表示取模的結(jié)果的向量表示 因而因而1的階為的階為8，即在高斯算法，即在高斯算法中中t1=8。由于。由于t1q-1=24，因而，因而1不是本原元，接著轉(zhuǎn)至第不是本原元，接著轉(zhuǎn)至第3步，步，需要選擇一個(gè)不是需要選擇一個(gè)不是1的冪次的的冪次的元素元素， 例如可以選例如可以選=(1,1)=x+1，則，則 2=(x+1)2 2x+3(modx2-2)=(2,3)，類似地可以得到類似地可以得到的各個(gè)冪次對(duì)的各個(gè)冪次對(duì)f(x)取模的結(jié)果的向量表示如下取模的結(jié)果的

44、向量表示如下 i1i0(0,1)1(1,0)2(0,2)3(2,0)4(0,4)5(4,0)6(0,3)7(3,0)8(0,1)表表6-5 1=(1,0)=x的的各個(gè)各個(gè)(gg)冪次的向量表冪次的向量表示示第40頁/共67頁第四十頁，共67頁。二、本原二、本原(bnyun)元元 因而因而的階為的階為12，進(jìn)而，進(jìn)而1=(1,0)，=(1,1)，t1=8，s=12，轉(zhuǎn)到第四步。轉(zhuǎn)到第四步。由于由于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=1

45、4=1(21+2)=212+21=2x2+2x2x+4(mod x2-2)且且2的階為的階為lcm(8,12)=24。因而。因而t2=24，返回，返回(fnhu)第二步，第二步，算法停止；算法停止；2x+4即為即為F中的本中的本原元。原元。ii0(0,1)1(1,1)2(2,3)3(0,2)4(2,2)5(4,1)6(0,4)7(4,4)8(3,2)9(0,3)10(3,3)11(1,4)12(0,1)第41頁/共67頁第四十一頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式設(shè)設(shè)F是有是有pm個(gè)元素的有限域，則由前面的討論個(gè)元素的有限域，則由前面的討論F可以看可

46、以看做是做是Fp上的一個(gè)上的一個(gè)m維向量空間。維向量空間。接下來接下來F，考察，考察F中的中的m+1個(gè)元素個(gè)元素1, , 2, m。由于由于F在在Fp上的維數(shù)為上的維數(shù)為m，因而這，因而這m+1個(gè)元素在個(gè)元素在Fp上必上必然是線性相關(guān)的，即存在不全為零的元素然是線性相關(guān)的，即存在不全為零的元素a0, a1, am，使得，使得a0+a1+a22+amm=0。即即是多項(xiàng)式方程是多項(xiàng)式方程a(x)=a0+a1x+a2x2+amxm=0的根。的根。當(dāng)然，當(dāng)然，也可以滿足其它多項(xiàng)式方程，因而可以定義也可以滿足其它多項(xiàng)式方程，因而可以定義S()為所有為所有(suyu)這樣的多項(xiàng)式構(gòu)成的集合，即這樣的多項(xiàng)式

47、構(gòu)成的集合，即S()=f(x)Fpx: f()=0。 第42頁/共67頁第四十二頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式設(shè)設(shè)p(x)為集合為集合S()中次數(shù)最低的非零多項(xiàng)式，中次數(shù)最低的非零多項(xiàng)式，f(x)為集合為集合S()中的任意多項(xiàng)式。則由帶余數(shù)除法，可以找到多項(xiàng)中的任意多項(xiàng)式。則由帶余數(shù)除法，可以找到多項(xiàng)式式q(x)與與r(x)，使得，使得f(x)=q(x)p(x)+r(x)，deg(r)deg(p)但是由于但是由于f()=p()=0，因而，因而r()=0。這與。這與deg(p)的最小性的最小性相矛盾，因而相矛盾，因而r(x)=0，進(jìn)而集合，進(jìn)而集

48、合S()中的任意多項(xiàng)式中的任意多項(xiàng)式f(x)都是都是p(x)的倍式。的倍式。稱集合稱集合S()中次數(shù)最低的這個(gè)多項(xiàng)式中次數(shù)最低的這個(gè)多項(xiàng)式p(x)為域?yàn)橛騀中以中以為根為根的最小多項(xiàng)式。若要求的最小多項(xiàng)式。若要求p(x)是首一多項(xiàng)式，則是首一多項(xiàng)式，則這樣的這樣的p(x)是唯一的，并且是不可是唯一的，并且是不可(bk)約多項(xiàng)式。約多項(xiàng)式。這是由于，若這是由于，若p(x)=a(x)b(x)，則由于，則由于p()=0，必然會(huì)得到，必然會(huì)得到a()=0或或b()=0，這與，這與deg(p)的最小性相矛盾。的最小性相矛盾。第43頁/共67頁第四十三頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原

49、(bnyun)多項(xiàng)式多項(xiàng)式定理定理(dngl)設(shè)設(shè)F是有是有pm個(gè)元素的有限域，則個(gè)元素的有限域，則F，若，若Fpx中存在唯一的首一多項(xiàng)式中存在唯一的首一多項(xiàng)式p(x)，使得，使得p()=0，deg(p)m，若若f(x)為為Fp(x)中另外一個(gè)以中另外一個(gè)以為根的多項(xiàng)式，則為根的多項(xiàng)式，則p(x)|f(x)。則稱則稱p(x)為為的相對(duì)于的相對(duì)于F的子域的子域Fp的最小多項(xiàng)式，的最小多項(xiàng)式，若若為本原元，則稱其所對(duì)應(yīng)的最小多項(xiàng)式為為本原元，則稱其所對(duì)應(yīng)的最小多項(xiàng)式為本原多項(xiàng)式。本原多項(xiàng)式。第44頁/共67頁第四十四頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式例

50、計(jì)算例所給域中某些個(gè)元素的最小多項(xiàng)式。例計(jì)算例所給域中某些個(gè)元素的最小多項(xiàng)式。解：考慮元素解：考慮元素(1,0)的冪次，這里暫時(shí)將的冪次，這里暫時(shí)將(1,0)記為記為。首先首先0=1，若，若F中的元素中的元素就是就是Fp中的元素，則其最小中的元素，則其最小多項(xiàng)式將總是多項(xiàng)式將總是x-，因而，因而0=1的最小多項(xiàng)式為的最小多項(xiàng)式為x-1。接下來，考慮接下來，考慮自身。由于自身。由于不是不是F3中的元素，因而中的元素，因而x-也不是也不是F3中的元素。中的元素。然而，二維向量空間然而，二維向量空間F中的中的3個(gè)向量個(gè)向量1=(0,1)，=(1,0)，2=(0,2)必定是線性相關(guān)的。必定是線性相關(guān)的

51、。進(jìn)而進(jìn)而(jn r)可以得到一個(gè)以可以得到一個(gè)以為根的二次方程，由于為根的二次方程，由于2-20=2-21=0，因而因而的最小多項(xiàng)式為的最小多項(xiàng)式為x2-2，即定義域的多項(xiàng)式。，即定義域的多項(xiàng)式。第45頁/共67頁第四十五頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式接下來計(jì)算接下來計(jì)算(j sun)2的最小多項(xiàng)式，由于的最小多項(xiàng)式，由于=2=(0,2)，因而，因而其最小多項(xiàng)式為其最小多項(xiàng)式為x-2。接下來計(jì)算接下來計(jì)算(j sun)=3的最小多項(xiàng)式，首先計(jì)算的最小多項(xiàng)式，首先計(jì)算(j sun)得到它的三個(gè)冪次如下得到它的三個(gè)冪次如下0=1=(0,1)，=3

52、=(2,0)，2=6=(0,2)，由于由于2=20，因而，因而的最小多項(xiàng)式為的最小多項(xiàng)式為x2-2或者為或者為x2+1。接下來計(jì)算接下來計(jì)算(j sun)本原元本原元=(1,2)=x+2的最小多項(xiàng)式。首先的最小多項(xiàng)式。首先計(jì)算計(jì)算(j sun)得到它的三個(gè)冪次如下得到它的三個(gè)冪次如下0=1=(0,1)，=(1,2)，2=(x+2)2x(mod x2-2)=(1,0)，由于由于2=+0，因而，因而的最小多項(xiàng)式為的最小多項(xiàng)式為x2-x-1或者為或者為x2+2x+2。第46頁/共67頁第四十六頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式以下以下(yxi)設(shè)設(shè)F是有

53、限域，是有限域，K是是F的有的有q個(gè)元素的子域。個(gè)元素的子域。由前面的討論知可以將由前面的討論知可以將F看做是看做是K上的一個(gè)向量空間，上的一個(gè)向量空間，故故F中的元素的個(gè)數(shù)是中的元素的個(gè)數(shù)是K中的元素個(gè)數(shù)中的元素個(gè)數(shù)q的冪次。的冪次。同時(shí)同時(shí)q應(yīng)是某個(gè)素?cái)?shù)應(yīng)是某個(gè)素?cái)?shù)p的冪次，即的冪次，即q=pm。因而存在某整數(shù)因而存在某整數(shù)n，使得，使得|F|=qn=pnm。F，將定理中的素域，將定理中的素域Fp替換為替換為K，則，則可以得到可以得到的相對(duì)于域的相對(duì)于域K的最小多項(xiàng)式的最小多項(xiàng)式p(x)。為了得到為了得到p(x)的具體表達(dá)式，需要引入如下幾個(gè)引理的具體表達(dá)式，需要引入如下幾個(gè)引理第47頁/

54、共67頁第四十七頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式引理引理 F，則，則K當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q=。特別地，。特別地，xK，有方程，有方程xq-x=0。證明：證明：K，若若=0，則，則q=；否則設(shè)否則設(shè)ord()=t，則，則t|(q-1)，因而，因而q-1=1，故，故q=，即即K中的中的q個(gè)元素為方程個(gè)元素為方程xq-x=0提供了提供了q個(gè)不同的解。個(gè)不同的解。同時(shí)同時(shí)(tngsh)該方程也就只有這該方程也就只有這q個(gè)解，而無其它解。個(gè)解，而無其它解。第48頁/共67頁第四十八頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)

55、式引理引理 若若p為素?cái)?shù)為素?cái)?shù)(s sh)，則對(duì)于，則對(duì)于1kp-1，有，有p整除二項(xiàng)式系數(shù)整除二項(xiàng)式系數(shù) 。證明：由二項(xiàng)式系數(shù)的定義有證明：由二項(xiàng)式系數(shù)的定義有該分?jǐn)?shù)的分子被該分?jǐn)?shù)的分子被p整除，但分母不被整除，但分母不被p整除。整除。 kp1)1()1()1( kkkpppkp第49頁/共67頁第四十九頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式引理設(shè)引理設(shè)1, 2, , t是任意是任意p特征域中的元素，則特征域中的元素，則k=1,2,3,證明：首先當(dāng)證明：首先當(dāng)t=1時(shí)，結(jié)論成立時(shí)，結(jié)論成立(chngl)。當(dāng)當(dāng)t=2時(shí)，利用數(shù)學(xué)歸納法證明時(shí)，利用數(shù)學(xué)歸

56、納法證明 k=1,2,3,。若。若k=1，上述等式中的每個(gè)二項(xiàng)式系數(shù)都是上述等式中的每個(gè)二項(xiàng)式系數(shù)都是p的倍數(shù)，進(jìn)而在的倍數(shù)，進(jìn)而在p特特征域中這些系數(shù)都是征域中這些系數(shù)都是0。因而。因而 。kkkkptpppt 2121)(kkkppp )(pppppppp 1111)(ppp )(第50頁/共67頁第五十頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式若若k=2，則，則因而當(dāng)因而當(dāng)k=2時(shí)結(jié)論成立。時(shí)結(jié)論成立。以此以此(y c)為基礎(chǔ)，由數(shù)學(xué)歸納法知為基礎(chǔ)，由數(shù)學(xué)歸納法知t=2時(shí)，等式時(shí)，等式 k=1,2,3,，成立。，成立。進(jìn)而，由數(shù)學(xué)歸納法知結(jié)論成立。進(jìn)

57、而，由數(shù)學(xué)歸納法知結(jié)論成立。222)()()(pppppppp kkkppp )(第51頁/共67頁第五十一頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式一般有限域中的最小多項(xiàng)式。一般有限域中的最小多項(xiàng)式。首先若首先若Kx中的多項(xiàng)式中的多項(xiàng)式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)的根

58、，則的根，則q也是也是p(x)的根。利用同樣的根。利用同樣的推導(dǎo)過程的推導(dǎo)過程(guchng)，我們會(huì)發(fā)現(xiàn)，我們會(huì)發(fā)現(xiàn), 等等也等等也都是都是p(x)的根。的根。第52頁/共67頁第五十二頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式定義稱定義稱，q，, 為為相對(duì)于子域相對(duì)于子域K的共軛根系，并稱的共軛根系，并稱(bn chn)此共軛根系中的元素個(gè)數(shù)為此共軛根系中的元素個(gè)數(shù)為的次數(shù)，的次數(shù)，記為記為deg()。定理定理 設(shè)設(shè)F是有是有qn個(gè)元素的有限域，則個(gè)元素的有限域，則F，若，若相對(duì)于相對(duì)于子域子域K的共軛根系中的元素個(gè)數(shù)為的共軛根系中的元素個(gè)數(shù)為d，則，

59、則d|n且且d是滿是滿足同余式足同余式qd1(modt) 的最小正整數(shù)，其中的最小正整數(shù)，其中t=ord()。同時(shí)同時(shí) t，若，若t=d+r，且，且0rd-1，則，則rtqq 第53頁/共67頁第五十三頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式證明：假設(shè)證明：假設(shè)0，則由于，則由于相對(duì)于子域相對(duì)于子域K的的各共軛根的的各共軛根都是有限都是有限(yuxin)域域F中的元素，因而序列中的元素，因而序列, q, , 中必定會(huì)出現(xiàn)重復(fù)。中必定會(huì)出現(xiàn)重復(fù)。 設(shè)設(shè) 為序列為序列, q, , 中最先出現(xiàn)重復(fù)的元素，中最先出現(xiàn)重復(fù)的元素，且且 ，其中，其中jd，則，則 因

60、而因而ord()|qj(qd-j-1)。但。但ord()|(qn-1)，即即gcd(ord(), qj)=1。因而。因而ord()|(qd-j-1)，即即 ，也即，也即 也是出現(xiàn)了重復(fù)的元素，但也是出現(xiàn)了重復(fù)的元素，但是最先出現(xiàn)重復(fù)的元素。因而是最先出現(xiàn)重復(fù)的元素。因而j=0，即，即2q 2q dq jdqq )1( jdjjdqqqqe jdqjdq dq dq第54頁/共67頁第五十四頁，共67頁。三、最小多項(xiàng)式與本原三、最小多項(xiàng)式與本原(bnyun)多項(xiàng)式多項(xiàng)式但但F中有中有qn個(gè)元素，因而個(gè)元素，因而因而因而 。由于。由于 是最先出現(xiàn)重復(fù)的元素，因是最先出現(xiàn)重復(fù)的元素，因而必定有而必定