数论与有限域-第六章

《数论与有限域-第六章》由会员分享，可在线阅读，更多相关《数论与有限域-第六章（67页珍藏版）》请在金锄头文库上搜索。

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得到 k-1

6、=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中的一个元素。由于p(

8、)=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个根的二次方程，这似乎与我们给出的引理6.2.1矛盾

9、。但是需要注意的是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当且仅当ord()|s。

10、 其次，设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,7的阶的结果如下表：

11、表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阶元素； 若t|(q-1)，

12、则在域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，分子与n相对互素，则 |Sn

13、|=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相对互素。 然而，由定理6.2.3应有 (1)+(5)

14、+(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)。,一、元素的阶,推论6.2.2 在每个有限域中，都至少存

15、在一个（事实上恰有(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,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中的本原元。,