信道编码-代数基础

第二章代数基础一、整数的一些基本性质1.基本概念素数合数因数（约数）素因数公约数最大公约数（greatestcommondivisor)a,b的最大公约数记为GCD(a,b)或(a,b)最小公倍数(leastcommonmultiple）a,b的最小公倍数记为LCM(a,b)或[a,b]2.整数的初等运算及性质加、减、乘、除定理1。任何正整数a均可唯一地分解为素因数的积。a=p1r1p2r2……pnrn(p1、p2、……pn素数，r1、r2、……、rn为正整数）《水浒》天罡星：36＝22×32地煞星：72＝23×32好汉：108＝22×32+23×32=22×32（1＋2）＝22×333.欧几里德除法（求最大公约数）定理2（欧几里德除法）：设b是正整数，则任意大于b的正整数a可唯一地表示为：a=qb+r0rb解释：两个正整数相除，商和余数是唯一的。定理3：a、b为正整数，且ab,设a=bq+r,则(a,b)=(b,r)。解释：利用欧几里德除法求最大公约数。例2.1.求(150,42)150=342+2442=24+1824=18+618=36(150,42)=(42,24)=(24,18)=(18,6)=6求（a,b,c)=((a,b),c)4.欧几里德算法定理4：给定任意a、b，(a,b)=Aa+Bb,(A、B为整数）。解释：两个正整数的最大公约数可表示为它们的线性组合。如何求？(150,42)150=342+2442=24+1824=18+618=36(150,42)=(42,24)=(24,18)=(18,6)=6（150，42）=24-18=24-（42-24）=224-42=2(150-342)-42=2(150-342)-42=2150-7425.最小公倍数(1)法1（利用定理1）：把a、b分解为素因子，取不同素因子最高次幂的积。[198，240，360]198=23211240=2435360=23325[198，240，360]=2432115=7920法2.I.求两个正整数的GCM定理5：若a、b为正整数，[a,b]=ab/(a,b)5.最小公倍数(2)求：[24871,3468]II.求两个以上正整数的GCM[a,b,c]=[[a,b],c]求：[198,240,360]6.同余和剩余类①同余(余数相同）：a、b、m为正整数，由欧几理德除法，a,b可唯一地表示为：a=q1m+r1b=q2m+r2若r1=r2,则称a,b关于模m同余，记为ab(modm)6.同余和剩余类(2)②模m的剩余类（同余）：全体整数按模m同余的分为一类，共有m类，称为模m的同余或剩余类，记为：1...,,10m，或{0}，{1}，…,{m-1}定义：{a}+{b}={a+b}{a}.{b}={a.b}定理6：若a1b1(modm),a2b2(modm),则（1）a1+a2b1+b2(modm);(2)a1.a2b1.b2(modm).a1a2b1b2a1+a2b1+b2同余二、代数系统1.映射：A-B单射、满射、双射（一一对应映射）2.变换：A=B的映射（到自身的映射）单变换、满变换、一一变换(置换)、恒等变换（aA:(a)=a)3.同态与同构同态：若映射：A-B满足条件：a1,a2A:(a1a2)=(a1)*(a2)，则称为A到B的同态映射，其中,*分别为集合A和B的运算。称A与B同态。同构：若同态映射为双射（课本有错），则称为同构映射，称A与B同构。a1a2(a1)a1a2AB(a2)(a1)*(a2)a3ba1a2(a1)a1a2AB(a2)(a1)*(a2)同态同构三、群Group只有一种运算的代数系统1.定义：设G是非空集合，并在G定义了一种代数运算“”，若下述公理成立，则称G为群，记为(G,）：(1)满足封闭性：a,bG:abG;(2)结合律成立：a,bG:（ab）c=a(bc);(3)存在恒等元：eG:aG:ae=ea=a;(4)每一元素存在逆元：aG:a-1G:aa-1=a-1a=e.群的阶：|G|有限群：|G|无限群：|G|=阿贝尔群、交换群：a,bG:ab=ba.例：全体整数对于加法构成群，对乘法不构成群。全体偶数对于加法构成群，对乘法不构成群。全体实数R对于加法构成群，对乘法不构成群，但R-{0}对乘法构成群。恒等元为01.群的定义（2）全体矩阵对矩阵加法构成群，恒等元为零矩阵。满秩矩阵对矩阵乘法构成群，恒等元为单位矩阵。模m的同余全体{0}，{1}，…,{m-1}在模m加法运算下构成群。-{n}={m-n}A={1,2,3}置换1,2,3定义为：213321132321321321321，，，，：，，，，，：，，，，，：定义为置换的复合，即12(a)=1(2(a)),则S={1,2,3}对构成群，称为置换群。312321123321231321324，，，，：，，，，，：，，，，，：3!=6,定义，则S3={1,2,3,4,5,6}对构成群，称为对称群（定义2.2.11)历史上人们很早就已经知道了一元一次和一元二次方程的求解方法。关于三次方程，我国在公元七世纪，也已经得到了一般的近似解法，这在唐朝数学家王孝通所编的《缉古算经》就有叙述。到了十三世纪，宋代数学家秦九韶在他所著的《数书九章》的“正负开方术”里，充分研究了数字高次方程的求正根法，也就是说，秦九韶那时候已得到了高次方程的一般解法。在西方，直到十六世纪初的文艺复兴时期，才由意大利的数学家发现一元三次方程解的公式——卡当公式。在数学史上，相传这个公式是意大利数学家塔塔里亚首先得到的,后来被米兰地区的数学家卡尔达诺(1501～1576年)骗到了这个三次方程的解的公式，并发表在自己的著作里。所以现在人们还是叫这个公式为卡尔达诺公式(或称卡当公式)，其实，它应该叫塔塔里亚公式。三次方程被解出来后，一般的四次方程很快就被意大利的费拉里(1522～1560年)解出。这就很自然的促使数学家们继续努力寻求五次及五次以上的高次方程的解法。遗憾的是这个问题虽然耗费了许多数学家的时间和精力，但一直持续了长达三个多世纪，都没有解决。法国数学家拉格朗日更是称这一问题是在“向人类的智慧挑战”。1770年，拉格朗日精心分析了二次、三次、四次方程根式解的结构之后，提出了方程的预解式概念，并且还进一步看出预解式和方程的各个根在排列置换下的形式不变性有关，这时他认识到求解一般五次方程的代数方法可能不存在。此后，挪威数学家阿贝尔利用置换群的理论，给出了高于四次的一般代数方程不存在代数解的证明。伽罗华通过改进数学大师拉格朗日的思想，即设法绕过拉氏预解式，但又从拉格朗日那里继承了问题转化的思想，即把预解式的构成同置换群联系起来的思想，并在阿贝尔研究的基础上，进一步发展了他的思想，把全部问题转化或归结为置换群及其子群结构的分析。这个理论的大意是：每个方程对应于一个域，即含有方程全部根的域，称为这方程的伽罗华域，这个域对应一个群，即这个方程根的置换群，称为这方程的伽罗华群。伽罗华域的子域和伽罗华群的子群有一一对应关系,这样，伽罗华把代数方程可解性问题转化为与方程相关的置换群及其子群性质的分析问题，这就是伽罗华工作的重大突破。对于任一个取有理数值的关于根的多项式函数，伽罗华群中的每个置换都使该函数的值不变。反过来，如果伽罗华群中的每个置换都使一个根的多项式函数的值不变，则这多项式函数的值是有理的。因此一个方程的伽罗华群完全体现了他的根（整体）的对称性。伽罗华的工作主要基于两篇论文──“关于方程根式解的条件”和“用根式求解的本原方程”。在这些论文中，伽罗华将其理论应用于代数方程的可解性问题，由此引入了群论的一系列重要概念。在《关于方程代数解法论文的分析》中，伽罗华提出了一个重要定理（未加证明）：一个素数次方程可用根式求解的充要条件是这个方程的每个根都是其中两个根的有理函数。伽罗华用它判别特殊类型方程的根式解问题。2.群的性质定理7：群(G,）具有如下性质：(1)恒等元是唯一的，每个元素的逆元也是唯一的。（定理2.2.1)(2)a,bG:(ab)-1=b-1a-1。（定理2.2.2)(3)a,bG:方程ax=b有唯一解x=a-1b;方程ya=b有唯一解y=ba-1。（定理2.2.3)(4)消去律成立：ax=ayx=y。3.半群与弱群半群：无恒等元，当然也无逆元（定义2.2.9）弱群（Monoid群，类群）：有恒等元，无逆元（定义2.2.10）4.子群（1）定义：群(G,）的非空子集H对于构成群，称H为G的子群。G,{e}:假子群，平凡子群HG且H{e}:真子群（2）定理8：群(G,）的非空子集H为子群的充要条件：①i.a,bH:abH(对H的封闭性），且ii.aH:a-1H(逆元也在H内）。或②a,bH:ab-1H。5.有限群的陪集群G:e,g1,g2,…子群H:h1=e,h2,h3,…若g1H,则用g1构成一个集合g1H:g1,g1h2,g1h3,…。叫H的左陪集若g2H且g2g1H，用g2构成第2个左陪集g2H:g2,g2h2,g2h3,…。G={{0},{1},…{8}}对模9加构成群H={{0},{3},{6}}对模9加构成子群{1}+H={{1},{4},{7}}{2}+H={{2},{5},{8}}定理9（陪集的性质）(1)两个陪集g1H，g2H满足：i.g1Hg2Hg1Hg2H=ii.g1Hg2Hg1H=g2H陪集之间不会相交,可见，有限群G可以按H划分为有限个不交的陪集，个数为|G|/|H|问题：陪集是从什么概念抽象出来的？5.有限群的陪集(2)(2)拉格朗日（Lagranges)定理：子群的阶一定是群的阶的因子6.正规子群（不变子群）(1)定义：设H为G的子群，若aG:aH=Ha,称H是G的正规子群。(2)定理10：子群(H,)为(G,)的正规子群的充要条件：aG，hH:a-1haH(定理2.4.4)(3)定理11（子群的性质）：设(H,)为(G,)的正规子群，定义G的两个陪集aH和bH的运算*为：（aH）*（bH）=（ab)H，则正规子群的陪集对*构成群。G={{0},{1},…{8}}对模9加构成群，H={{0},{3},{6}}对模9加构成子群{1}+H={{1},{4},{7}}，{2}+H={{2},{5},{8}}（{1}+H)+H={1}+H({1}+H)+({2}+H)=H7.商群G={{0},{1},…{8}}对模9加构成群H={{0},{3},{6}}对模9加构成子群{1}+H={{1},{4},{7}}{2}+H={{2},{5},{8}}（{1}+H)+H={1}+H({2}+H)+H={2}+H({1}+H)+({2}+H)=H{H,{1}+H,{2}+H}对+构成群。商群是构成新群的方法之一。定义：群G的正规子群H的全体陪集构成的群称为G关于H的商群，记为G/H。四、环与域1.环定义：非空集合R中，定义了两种代数运算“+”和“*”，若满足下述公理，则称R构成一个环，记为（R,+,*)。(1)R在+下构成阿贝尔群；(2)运算*满足封闭性：a,bR:a*bR;(3)运算*结合律成立：a,bR:(a*b）*c=a*(b*c);(4)*对+的分配律成立：a,b,cR:a*(b+c)=a*b+a*c且(b+c)*a=b*a+c*a可见，R在*下为半群，不一定有恒等元，当然也不一定有逆元。若有恒等元（这时为弱群），称为有单位元环。若每个非零元素有逆元，但