有限群的一个应用.doc

有限群的一个应用王绍恒（四川三峡学院计算机系，重庆市万州区 404000）摘要：本文证明了由n阶群的n-1个元完全决定第n个元，并给出了交换群中第n个元的求法，最后给出两个应用实例。关键词：有限群；元素；应用中图分类号 O152 文献标识码A1引言 由文1，一个n阶群的生成元的最少个数不大于，在实际应用中，一个群的已知元素当然可以比生成元多，下面讨论非常特殊的情况。如果已经给出了群的n-1个元素，第n个元素是否唯一确定？如何确定？2主要结论定理1 设G为一个n阶群，若已知其中n-1个元素，则第n个元素被唯一确定。证明：因有限群的运算规则可由乘法表给出2，设G中n-1个元 * x1 x2 xn-1 xnx1, x2, , xn-1之间的乘法如乘法表所示。 x1 a11 a12 a1,n-1 由于单位元对应行的元素与乘法表中第一行相同，如果x1, , xn-1 x2 a21 a22 a2,n-1 对应的行均不与第一行相同，则xn就是单位元。如果x1, , xn-1中有某 元（不妨设x1）对应的元素与第一行对应的元素相同，则x1为单位元。 xn-1 an-1,1 an-1,2 an-1,n-1 这时x2x1, x2x2, , x2xn-1中必有一项等于xn，否则只有x2xn=xn，推出 xnx2也为单位元，与单位元的唯一性矛盾。但由x1为单位元知，xn未出现在x1x1, x1x2, , x1xn-1中，因此x2所在行中对应的元素里未在x1所在行出现的那一个元就是G的第n个元素xn。当G为交换群时，第n个元素可不借助乘法表直接计算。定理2 设G为奇阶交换群，且G=Ax，xA，则 x=.证明：考虑G的映射j：xx-1。j是G的一一映射，j(1)=1。当x1时j(x) x。否则x-1=x，得x2=1。于是2|G|，与G为奇阶群矛盾。从而G中元除1外在j下两两配对，每一对之积为1。由G为交换群，得=1，从而x=1。因此x=偶数阶群总有2阶元素，我们将2阶元素称为对合3。基金项目：国家自然科学基金（批准号19871066）及教育部重点科学技术资助项目作者简介：王绍恒(1962 - )，男(汉族)，重庆人，讲师，主要从事群论研究。定理3，设G为偶数阶交换群，且G=ABx，其中A为不含x的非对合元，B为不含x的对合元，则x=g0，其中g0为某一个对合。证明：把G中的元分成两类：A0=非对合之集，B0=对合之集。由定理2知，G中所有非对合元之积为1，又因交换群中任意两个对合之积仍为对合，从而有，g0为某一个对合,由此即得=g0。从而x=g0。推论1：设G=为n阶循环群，又G=Ax，xA，则当n为奇数时，x=，当n为偶数时，x=。 证明：因x=当n为奇数时，当n为偶数时，3应用实例例1 设有一组卡片，每张卡片为红、黄、兰三种颜色之一，并有一个编号，编号的第一位为字母AZ，第二、三位为数字0099。编号各不相同，因此一共有326100=7800张卡片。这组卡片分别由甲、乙两人各保存一部份（张数不必相同），现在有一张卡片丢失，怎样把这张丢失卡片的特征找出来？（假定甲、乙两人的卡片不能放到一起）。找法如下：第一步：以0，1，2分别代表红、黄、兰三种颜色，用群Z3表示。以0，1，25分别代表字母A，B，Z这26个字母，用群Z26表示。以0，1，99分别代表数字00，01，99这100个数字，用群Z100表示。于是所有卡片的颜色及编号与交换群G=Z3Z26Z100中元素一一对应，丢失的卡片的特征对应于G中“丢失”的一个元素。第二步，取出甲现有全部卡片，求出（1黄色张数+2兰色张数）3的余数，记为a1。求出（1字母B的张数+2字母C的张数+25字母C的张数）26的余数，记为b1。求出（1数字01的张数+2数字02的张数+99数字99的张数）100的余数，记为c1。取出乙现有全部卡片，类似地求出a2，b2，c2。第三步：设a1+a2a (mod 3) 0a3因3为奇数，由推论1，Z3中的丢失元为a的逆元3-a。设b1+b2b (mod 26 ) 0b26因26为偶数，由推论1，Z26中“丢失”的元为b的逆元26-b再加上13，但Z26中每元都求了1003次和，故G中共有300个13，其总和0(mod 26)，因此G的“丢失”元的第二分量仍取26-b。设c1+c2c (mod1 00) 0c100因100为偶数，由推论1，Z100中“丢失”的元为c的逆元100-c再加上50，但Z100中每元都求了263次和，故G中共有78个50，其总和0(mod 100)，因此G的“丢失”元的第三分量仍取100-c。最后得数组（3-a，26-b，100-c）就是所丢失的卡片的颜色和编号的特征。例如数组（2，10，69）对应的卡片为兰色，编号k69。例2 设一个密码由六位数字组成，为了加强保密性，可由n个人（n106）共同保管，使其中任何1至n-1个人都无法知道这个密码，必须n个人同时配合才能知道。保存办法：将106张卡片编号为000000 999999，从中随机抽取一张，取其编号作为密码，把余下的106-1张卡片随意分成n部分后由n个人分头保管。这样，其中任何1至n-1个人都无法查出该密码，但n个人合作可以查出，例如将n个人的卡片集中在一起核查所缺的编号就可查出密码，但这样很麻烦，我们仍利用推论1按如下办法进行查找：第i个人把他保管的卡片的编号相加，再除以106取余数ai。设 （mod 106）由推论1，密码号就是 （mod 106）。也就是说，当时，密码号为，当时，密码号为。在实用中，每个人都不必记住他所保管的每张卡片的编号，只需记住上文中的ai即可，而且这种保存密码的方案其保密性很高。以5个人共同保管为例，假如每人保存同样张数的卡片（其中有一人比其余人少一张），则k个人合作一次可猜中密码的概率为，当k分别取1，2，3，4时，这个概率值分别为1.2510-6, 1.6710-6, 2.510-6, 510-6,这个概率值非常小，而且还要把k个人的卡片编号集中起来排除2k105个编号后再任猜一个6位数才有这样的概率。4需进一步讨论的问题最后，本文提出如下需进一步讨论的问题：1 当群G是非交换群时，如何不借助乘法表由G的n-1个元素求余下的第n个元素？2 如果群G中缺少的元素不只一个，能否唯一地定出G的其余元素？若能，缺少的元素最多能达到多少（当然不会比非生成元还多！）？衷心感谢导师施武杰教授的悉心指导和鼓励。An application of Finite GroupsWANG Shao-heng(Comp. Dept. The Si Chuan Three Gorges College，Chongqing 404000,Chian)Abstract In this paper, let the order of the finite group G is n. It will prove that the nth element of G has been decided completely by remainder n-1 elements in group G. We shall give a method of finding the nth element of G and two examples for application of it.Keywords finite group; element; application.参考文献1 Derek J. S. Robinson, A Course in the Theory of Groups M, Springer-Verlag. Berlin-