hrbust acm培训教程-icpc课件2群论

1、群论基础知识半群二元运算：连接两个元素的运算符，例如+-*/定义1：一个代数系统,其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭(二元运算的结果在群内)的，则称代数系统为广群。定义2：在中（1）运算*是封闭的；（2）运算*是可结合的，即对任意x,y,zS，满足(x*y)*z = x*(y*z)则称代数系统为半群。半群就是在广群的基础上多了结合行的限制定理1：设是一个半群,B是S的子集合，且*在B上是封闭的，那么是一个半群，通常称B是S的子半群。定理1的证明：因为*在S上是满足结合性的，而B属于S且*在B上满足封闭性，所以*在B上是满足结合行的，由定义二可知是一个半群定理2：设是一个

2、半群，如果S是一个有限集，则必有aS，使得a*a=a。定理2的证明：（看了离散数学的教材，感觉有个地方的证明不是很严密，自己试着证明了一下，以下为自己的证明）。证明定理二所需的推论(1):设bS，我们用b2表示b*b，b3表示b*b*b依次类推，由于S是有限集所以定存在某一m使得bm等于b（xm）;证明定理二所需的推论(2):这里令bm为第一个不同于b（x 1时，我们利用反证法，设bm=bx（x1），可知bm-1*b = bm = （bx-1）*b1bm-1 = bx-1与bm为第一个不同于b（xm）的元素相悖证明定理2所需的推论（3）：由推论（2）可知bm = b1则b1*b1 = bm*b

3、1b2 = bm+1，依次类推可知b1，b2，b3.会构成无限次循环，每次循环的长度相同。定理2的证明部分：由推论（3）可知，令m为 循环长度，bx+bm = bx（x=m)则当x = m时，bx*bx = bm+bm = bm=bx定义3：含有幺元的半群叫做独异点群(S,)是一个集合S和定义在S上的二元运算，具有如下性质1.封闭性：对所有a，bS有abS2.单位元：存在一个元素eS，满足对所有aS，ea=ae=a。3.结合律：对所有a,b,cS有 (ab)c = a(bc)4.逆元:对每个aS，存在唯一一个bS有ab=ba=e如果群满足交换律，即ab = ba，则它是一个交换群。如果群(S,

4、)满足|S| ，则它是一个有限群定理3：群中不可能有零元（a*0 = 0）定理三的证明:与幺元定义相悖。定理4：设是一个群对于a，b属于S，必存在xS使得a*x=b。定理4的证明：设a的逆元为a-1a*x=b则有a-1*a*x=a-1*b则x=a-1*b，易知x是唯一的。定理5：设是一个群，对任意a,b,c属于S，如果a*b=a*c或者b*a=b*c则必有b=c；子群子群：如果是一个群，集合G属于S，且是一个群，我们称是的子群。定理6：如果是一个有限群，如果集合G是S的任意一个非空子集并满足任意a,bG，a*bG，则为的子群。定理6的证明：在证明定理2所用的推论（3）中，我们已经证明了在半群中

5、b作为生成元所生成的新元是循环的（我们用同种方法可以证明此推论在群中同样适合），设m为循环长度，得bm*b1=b1，由于可以知道bm在中是单位元，则在G中bm是单位元。并且我们可以知道，对任意一个bx都有b（m-x）使得bx*b（m-x） = bm = e，bx与b（m-x)互为逆元。至此已经证明了满足所有群的性质。单射，满射与双射单设：设f是由集合A到集合B的映射，如果x,yA,且xy等价于f(x)f(y),则称f为由A到B的单射。满射：若函数为满射，则对任意b，存在a满足f(a) = b。双射：既是单射又是满射的函数。双射（单射与满射） 单射但非满射 满射但非单射非满射非单射定义：设S是一个非空集合，从S到S的一个双射叫做S的一个置换。Poj1845题目大意：找出ab的因子的和答案对9901取模我们将a可变成这样e1x1*e2x2.（ei为素数）答案就变成这样(e10+e11.e1x1)*(e20+e21.e2x2).用同余模定理我们可以知道每个e都能变成e%99