Lecture-2近世代数1内容vEuclidean算法v同余和剩余类v同态与同构v群v环v域v子群，正规子群，与商群v子格与划分2Euclidean 算法v最大公约数同时除尽a, b, , l （不全为0）的最大正整数，记为( a, b, , l )或GCD ( a, b, , l)v最小公倍数同时被a, b, , l （不全为0）除尽的最小正整数，记为a, b, , l 或LCM ( a, b, , l)vEuclidean除法设b是正整数，则任意正整数ab皆可唯一地表示成 a=qb+r 0=rbvEuclidean算法对任意给定的正整数a, b,必存在整数A, B使(a, b)=Aa+Bbv性质：ab=(a, b) a, b3Euclidean 算法v例子:求595, 493595 493102 4931024+85102=85+17 85=175(595, 493)=17; 595, 493=(595493)/17=17255v例子: (595, 493)的Euclidean算法表示(595, 493)=17 =102-85 =102-(493-4102) =5102-493 =5(595-493)-493 =5595(-6)4934同余和剩余类v同余若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为若 则v剩余类给定正整数m，将全体整数按余数相同进行分类，可获得m个剩余类：v 例子25 4(mod 7); 12 5(mod 7); 2512=300 6(mod 7) 45(mod 7) m=35映射v 单值映射 设A和B是两个集合，如果存在某个对应法则f，使得对任一aA，都能唯一确定一个元素bB与之对应，则称f是A到B的一个单值映射。
称b是a在f下的像，a为原像v 满射 设f是集合A到集合B的单值映射，如果对任一bB，必然存在有aA，使得b=f(a)，则称f是A到B的满射v 单射，双射 如果对集合A中不同的元素，在f之下在集合B中有不同的像，即当且仅当a1=a2时，f(a1)=f(a2)，则称f是A到B的单射如果f既是满射又是单射，就称为双射或一一映射v 变换 设f是集合A到A的映射，则称f是A中的变换A到A的满射称为满变换，单射称为单变换，一一映射称为一一变换或置换如果变换保持A中的任一元素不变，则称为恒等变换或恒等置换6同态与同构v代数系统满足一定规律或定律的系统称为代数系统且有：有一群元素构成一个集合；在元素集合中有一个等价关系；在集合中定义了一个或数个运算，通过运算建立起元素之间的关系；有一组假定v同态与同构：设f是代数系统(A, )到(B,*)的映射，如果它满足条件 f(a1 a2) =f(a1) *f(a2) a1 ,a2 A, f(a1) ,f(a2) B 则称f是A到B的同态映射，集合A与B同态如果同态 映射f又是双射，则称为同构映射，集合A与B同构若f是A 到A自身的同构映射，则称为自同构7同态与同构v例子：(R,)和(R+,),这里，分别为数的加法和乘法。
规定映射f: RR+为f(x)=10 x, 则f是RR+的同构映射Proof：对于任何y R+,存在x=lgy使f(x)=y,所以f是RR+的满射；对任意的x, y R，如果10 x =10y ，得x=y，所以f为RR+的单射因此f是RR+的双射又由于f(xy)=10 x+y= 10 x 10y =f(x)f(y)，所以f是R到R+的同构映射整数集合与剩余类集合之间仅是同态映射（See Slide-5）8同态与同构v 设(Z, +)和(A, ), 这里A=1, -1, 规定映射f：ZA为对任何xZ, 证明： f是ZA的同态映射Proof: 对于任何x, y Z 如果x, y都是偶数，则f(x)=1, f(y)=1，于是 f(x+y)=1=11=f(x)f(y)(2) 如果 x, y都是奇数，则f(x)=-1, f(y)=-1 ，于是 f(x+y)=1=(-1)(-1)=f(x)f(y)(3) 如果 x是奇数， y是偶数，则f(x)=-1, f(y)=1，于是 f(x+y)=-1=(-1)1=f(x)f(y)同理可证： x是偶数， y是奇数时， f(x+y)=f(x)f(y)因此， f是ZA的同态映射。
QED9同态与同构v设有理数集Q，代数运算为数的加法，Q*为非零有理数集，代数运算为数的乘法，证明: (Q, +)与(Q*, )不存在同构映射Proof (反证法）：假定*存在同构映射f,并令f(0) = xQ*.再令f(x) = x0，于是 f(0+x)=f(0)f(x)=xx f(x)=xx x= xx x=1 f(0) =1 但另一方面，设f(a)=-1 f(a+a)=(-1) (-1)=1，但 f(0) =1，所以a+a=0a=0，于是又有f(0)=-1，这与f 是*的双射矛盾因此， Q与Q*不存在同构映射QED10群的定义v设G是一个非空集合，并在G内定义了一种代数运算 “ 若满足： v则称G构成一个群若加法，恒等元用0表示，若为乘法，恒等元称为单位元1) 封闭性对任意，恒有2) 结合律对任意，恒有3) G中存在一恒等元e,对任意，使4) 对任意，存在a的逆元，使11群实例v例子全体整数：对加法构成群；对乘法不构成群全体偶数：对加法构成群；对乘法不构成群全体实数：对加法构成群；对乘法构成群（除0元素）全体复数：对加法构成群；对乘法构成群（除0元素）全体有理数：对加法构成群；对乘法构成群（除0元素）模m的全体剩余类 ：对模m加法构成群；对模m乘法，除0外，根据m值不同有不同的结论。
如m=4时，剩余类 中的元素的逆元不存在如对模m=3乘法，除0外，剩余类全体构成群12群实例v设G=1, -1, i, -i, 为数的乘法，则(G, )是一个交换群因为，G中任意两个元的乘积还是G的一个元于是，G在下是封闭的数的乘法总是满足结合律和交换律G的单位元为1，且(-1) -1=-1, i-1=-i, (-i) -1=iv(S=1, 2, 3, 4, 6, 12, GCD)是群吗？任给a, b, cS, GCD(a, b) S, 所以S对GCD是封闭的 GCDGCD(a, b), c = GCDa, GCD(b, c) 满足结合律因为GCD(12, a)=a，所以的单位元为12因为GCD(1, a)=112，所以1没有逆元因此，(S, GCD)不是群13群性质v群的恒等元、每个元素的逆元都是唯一的Proof：反证法v若a, b G,则(a b)-1=b-1 Proof：直接代换v给定G中任意两个元素a和b ，方程a x = b和y a = b在G中有唯一解：x = a-1 b , y = b a-1v群G中消去律成立即由a x = a y x = y14群的相关概念v 群的阶(Order of a Group) 有限群(Finite Group)、无限群(Infinite Group)v 加群、乘群v 阿贝尔群(Abelian Group)、可换群、交换群：满足交换律 所有n阶满秩矩阵的全体对矩阵乘法构成的群为非阿贝尔群v 半群(Semigroup)(满足前两个条件) 如正整数在加法运算下构成一个半群（无恒等元）v 弱群(Monoid)(满足前三个条件) 整数在乘法运算下构成一个Monoid（无逆元）v 对称群(Symmetric Group) 由n个元素构成的集合A到自身的所有n!个置换构成的集合在置换运算下构成对称群。
15置换群v置换群(Permutation Group)例子：A=1, 2, 3置换群不一定是对称群；对称群一定是置换群在置换运算下构成置换群为单位元互为逆元16置换 3 7 1 9 8 5 0 9 5 7 0 8 1 3 3 8 7 0 1 9 51=(1, 3, 5, 6, 2, 7, 4)2= (4, 6, 2, 7, 5, 3, 1)17格（Lattice）v定义：格(Lattice)是一类加群，集合中的元素是欧氏空间中的离散点，称为格点例如：n维欧氏空间Zn中离散点的集合(Z1,Z2,Zn); Zi Z在矢量相加和相减运算下构成一整数格v几何性质最小均方距离 : 任意两个格点之间的最小均方距离格的基本体积 : 每一格点在n维空间的体积See Lecture 1-Slide 18v结构性质标量乘；正交变换；笛卡儿(Cartesian)积18偏序集v 定义：设P是任一集合，P上的一个二元关系记为“”，满足1）任给aP, a a（反身性）； 2）任给a, bP, ab并且ba则a=b （反对称性）； 3）任给a, b, cP, ab并且bc则a c （传递性）则称是P的一个偏序关系，具有偏序关系的集合P，称为偏序集，记为（P, ）。
v 例：设P=1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 如果偏序关系为整除关系，那么(P, )的偏序集合如下图139186122484219格（Lattice）v(alternative)设(L, )是一个偏序集，如果L中任意两个元素均有最小上界与最大下界，则称L关于偏序集作成一个格偏序集格0001101120环的定义v非空集合R中，若定义了两种代数运算加和乘，且满足：1) 集合R在加法运算下构成阿贝尔群2) 乘法有封闭性3) 乘法结合律成立，且加和乘之间有分配律v环阿贝尔加群乘法半群v例子全体整数；全体偶数；实系数多项式全体均构成环模整数m的全体剩余类构成剩余类环v相关概念有单位元环（乘法有单位元）交换环（乘法满足交换率）21环的相关概念v有零因子环对于环中的两个非零元素 a和b，若它们在环上定义的乘法运算下为零，即ab=0，则a、b为零因子，对应的环为有零因子环乘法消去率不成立例：Z6：23=6=0(mod 6); 23=03(mod 6) but 20v整环（无零因子环）乘法消去率成立例： Z5v除环有单位元、每个非零元素有逆元，非可换的环例如所有n阶实数满秩矩阵全体和全零矩阵构成除环22环vR=a+b51/2|a, bZ关于数的加法和乘法是否构成环？任给p, q R, p=a1+b151/2 , q=a2+b251/2 , a1, b1 , a2,b2 Z. p+q = (a1+b151/2 )+(a2+b251/2) = (a1+a2 ) +(b151/2 +b251/2) R pq = (a1+b151/2 ) (a2+b251/2) = (a1a2+5b1b2 ) +(a1b2 + a2b1 ) 51/2 R 显然，(R, +)是加群， (R, )是半群且乘法对加法满足 分配律，所以(R, +, )是环。
23域v定义：非空集合F，若F中定义了加和乘两种运算，且满足：1) F关于加法构成阿贝尔群，加法恒等元记为02) F中所有非零元素对乘法构成阿贝尔群，乘法恒等元 记为13) 加法和乘法之间满足分配律v域是一个可换的、有单位元、非零元素有逆元的环，且域中一定无零因子v有理数域；实数域；复数域v元素个数无限的域称为无限域；元素个数有限的域称为有限域，用GF(q)或Fq表示q阶有限域有限域也称为伽逻华域24域v 设p为素数，则整数全体关于模p的剩余类 在模p的运算下(模p加和乘)构成p阶域GF(p)Proof: (只需证非0元素有逆元）其中1为单位元，因为p为素 数，因此任意小于p的数a和p互素所以由Euclidean算法可知： (a, p)=1=Aa + Bp 在等式两边对p取模，则有 1 Aa (mod p) 所以剩余类中任一元素均有逆元Q.E.D.v Q.E.D. is an abbreviation of the Latin phrase quod erat demonstrandum (literally, that which was to be demonstrated). The p。