现代信息理论编码与技术chapter2.ppt

第二章 代数基础 陆以勤 2005年3月 一、整数的一些基本性质 基本概念 素数 合数 因数（约数） 素因数 公约数 最大公约数（greatest common divisor) a,b的最大公约数记为GCD(a,b) 或(a,b) 最小公倍数 (least common multiple） a,b的最小公倍数记为LCM(a,b) 或 [a,b] 整数的初等运算及性质 加、减、乘、除 定理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 × 33 3. 欧几里德除法（求最大公约数） 定理2（欧几里德除法）：设b是正整数，则任意大于b的正整数a可唯一地表示为： a=qb+r 0?r b 解释：两个正整数相除，商和余数是唯一的。 定理3：a、b为正整数，且ab, 设a=bq+r, 则(a,b)=(b,r)。 解释：利用欧几里德除法求最大公约数。 例2.1. 求(150,42) 150=3?42+24 42=24+18 24=18+6 18=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+24 42=24+18 24=18+6 18=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 ? 42 5. 最小公倍数(1) 法1（利用定理1）：把a、b分解为素因子，取不同素因子最高次幂的积。 [198，240，360] 198=2 ?32 ?11 240=2 4?3 ?5 360=2 3?32 ?5 [198，240，360]=2 4?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. 同余和剩余类(2) 模m的剩余类（同余）：全体整数按模m同余的分为一类，共有m类，称为模m的同余或剩余类，记为： 二、代数系统 1. 映射 ?：A - B 单射、满射、双射（一一对应映射） 三、群 Group 1.群的定义（2） 历史上人们很早就已经知道了一元一次和一元二次方程的求解方法。关于三次方程，我国在公元七世纪，也已经得到了一般的近似解法，这在唐朝数学家王孝通所编的《缉古算经》就有叙述。到了十三世纪，宋代数学家秦九韶在他所著的《数书九章》的“正负开方术”里，充分研究了数字高次方程的求正根法，也就是说，秦九韶那时候已得到了高次方程的一般解法。 在西方，直到十六世纪初的文艺复兴时期，才由意大利的数学家发现一元三次方程解的公式——卡当公式。在数学史上，相传这个公式是意大利数学家塔塔里亚首先得到的,后来被米兰地区的数学家卡尔达诺(1501～1576年)骗到了这个三次方程的解的公式，并发表在自己的著作里。所以现在人们还是叫这个公式为卡尔达诺公式(或称卡当公式)，其实，它应该叫塔塔里亚公式。 三次方程被解出来后，一般的四次方程很快就被意大利的费拉里(1522～1560年)解出。这就很自然的促使数学家们继续努力寻求五次及五次以上的高次方程的解法。遗憾的是这个问题虽然耗费了许多数学家的时间和精力，但一直持续了长达三个多世纪，都没有解决。法国数学家拉格朗日更是称这一问题是在“向人类的智慧挑战”。1770年，拉格朗日精心分析了二次、三次、四次方程根式解的结构之后，提出了方程的预解式概念，并且还进一步看出预解式和方程的各