近世代数1.ppt
应用近世代数应用近世代数 主讲：徐 音单位：三系一教第一章第一章 整数论整数论1.1 整数的可除性整数的可除性 1.2 欧几里德算法与同余式欧几里德算法与同余式 1.3 欧拉欧拉-费尔马定理费尔马定理 1.4 指数指数 本章小结本章小结一一、自然数和整数自然数和整数(1)N=0,1,2,n,任意两个自然数的和积仍然是自然数，任意两个自然数的和积仍然是自然数，但是两个自然数作减法运算的结果不一定但是两个自然数作减法运算的结果不一定是自然数，产生了负数和零。是自然数，产生了负数和零。1.自然数及其运算自然数及其运算一一、自然数和整数自然数和整数(2)Z=,-n,-2,-1,0,1,2,n,任意两个整数在集合任意两个整数在集合Z可以做加减和乘法可以做加减和乘法 运算，但做除法运算的结果不一定是整数。运算，但做除法运算的结果不一定是整数。2.整数及其运算整数及其运算二二、整除的概念整除的概念(1)定义定义1.1 整数集合整数集合Z中任意两个数中任意两个数a,b，如，如果存在一个果存在一个qZ，使得，使得a=bq，则称，则称b整除整除a，记为，记为b|a，也称，也称b是是a的因数，或的因数，或a是是b的的倍数。否则，称倍数。否则，称b不能整除不能整除a。1.整除的定义整除的定义二二、整除的概念整除的概念(2)性质性质1:如果如果a|b，则，则a|(-b)，(-a)|(b)，(-a)|(-b)性质性质2:如果如果a|b及及a|c，则，则a|mb+nc，m,nZ推广推广：如果：如果a|bi，则，则a|kibi i=1,2,n，ki Z2.整除的性质整除的性质二二、整除的概念整除的概念(3)性质性质3:如果如果a|b，b|c，则，则a|c。性质性质4:如果如果a|b，b|a，则，则a=b。性质性质5:如果如果a|b，c0，则，则ac|bc。性质性质6:如果如果ac|bc，c0，则，则a|b。二二、整除的概念整除的概念(4)定理定理1.1 设设a,b是整数集合是整数集合Z中任意两个中任意两个数且数且b0，则一定存在唯一的两个整数，则一定存在唯一的两个整数q和和r,使得使得 a=bq+r,0r1，且除了，且除了1和它本身外和它本身外没有其它因数，则没有其它因数，则a称为素数。称为素数。大于大于1 1不是素数的称为合数。不是素数的称为合数。性质性质1:一个素数一个素数p 和任一个整数和任一个整数a，则则p|a与与(p,a)=1,)=1,二者必有其一成立。二者必有其一成立。性质性质2:如果一个素数如果一个素数p|ab，则，则p|a或者或者p|b。1既不是素数既不是素数也不是合数也不是合数2.素数素数四四、互素与素数互素与素数(3)定理定理1.2 任何一个大于任何一个大于1 1的正整数的正整数a可以分解成有限可以分解成有限 个不同素因子的幂之积个不同素因子的幂之积,即即除因子的次序外，该分解是唯一的。上式又称为整除因子的次序外，该分解是唯一的。上式又称为整数的标准分解式。数的标准分解式。3.算术基本定理算术基本定理 定义定义1.7 如果素数如果素数p|a，则，则p称为称为a的素因子。的素因子。定理定理1.3 设两个整数设两个整数a与与b，则有，则有ab=(a,b)a,b第一章第一章 整数论整数论 1.1 整数的可除性整数的可除性1.2 欧几里德算法与同余式欧几里德算法与同余式 1.3 欧拉欧拉-费尔马定理费尔马定理 1.4 指数指数 本章小结本章小结一一、欧几里德算法欧几里德算法(1)1.求两个数的最大公因数求两个数的最大公因数定理定理1.4 若若ab0，且且 a=bq+r (0rb0，且，且则则对对a与与b做辗转相除，最后一个余数就是要求做辗转相除，最后一个余数就是要求的最大公因数。称为的最大公因数。称为“辗转相除法辗转相除法”。二二、整数按模运算整数按模运算(1)设设n是任意给定的正整数，是任意给定的正整数，a是一个整数，是一个整数，用用n除得到的商为除得到的商为q，余数为，余数为r，即：，即：a=nq+r,0rn用用(a)n表示用表示用n去除去除a得到的余式。得到的余式。1.带余除法带余除法二二、整数按模运算整数按模运算(2)2.按模运算按模运算设设n,a,b是正整数，是正整数，模模n加法：加法：a b=(a+b)n模模n乘法：乘法：a b=(ab)n0 a b n0 a b 1，(a，n)=1，能够使，能够使 ae1mod n成立的最小正整数成立的最小正整数e称为称为a mod n的指数。的指数。例：例：3mod4的指数为的指数为2，因为，因为 313 mod 4，321 mod 4 一一、指数指数(2)2.指数的性质指数的性质性质性质1:如果如果ab mod n 且且(a,n)=1，则，则a与与b有相同的指数。有相同的指数。性质性质2:设设n1,(a,n)=1，e为为amodn的指数，的指数，则则根据性质根据性质2可知，可知，a的指数在的指数在(n)的因子中寻找即可的因子中寻找即可性质性质3:如果如果n=n1n2,(n1,n2)=1，设，设amodni的指数为的指数为ei(i=1,2),amodn的指数为的指数为e，则则 e=LCM(e1,e2)一一、指数指数(3)性质性质4 设设 ，其中，其中pipj，pi,pj为为素数素数,ki 1，若，若(a,n)=1，设，设amodn的指数的指数为为e,amod 的指数为的指数为ei，则：，则：e=LCM(e1,e2,er)性质性质5 设设n1，(a,n)=1，e为为amodn的指数，的指数，ar modn的指数为的指数为e,则则
