初等数论最大公因数.pptx
定义：若=1，则称互素。若对,则称两两互素。显然两两互素可推出互素，反之不行。例（2，3，4）=1，但（2，4）=2。下面主要讨论两个数的最大公因数的性质.第1页/共23页性质：1、=2、(0,b)=|b|,b0.3、(a,b)=(b,a)前3条比较简单.4、若a=bq+c，则（a，b）=（b，c）分析:(1)可证(a,b)和(b,c)相互整除.(2)利用集合知识说明a,b和b,c的公因子集相同.第2页/共23页证：设d是a，b的任一公因数，则有d|a，d|b，则有d|c=a-bq，说明d也是b，c的公因数，反之设d是b，c的任一公因数，则d|b，d|c，则有d|a，说明d也是a，b的公因数。所以a，b的全体公因数的集合就是b，c的全体公因数的集合。则最大的一个也相等即（a，b）=（b，c）注：这个性质是后继知识的基础，很重要,因为两个较大的数的最大公因数可转化为较小的两个数的最大公因数,从而为求大公因数找到了方法.第3页/共23页为求两个数的最大公因数，引进辗转相除法辗转相除法：下面的一组带余数除法称为辗转相除法。设a，b为正整数，依次做带余除法第4页/共23页5、a，b为整数，则（a，b）=即最后一个不为零的余数证：由性质4知(a,b)=推论：a，b的公因数与（a，b）的因数相同。证：由辗转相除法d|a，d|b，则有d|（a，b），反之也对第5页/共23页例1、求24871与3468的最大公因数解：24871=3468*7+595，3468=595*5+493，595=493*1+102，493=102*4+85，102=85*1+17，85=17*5,所以(24871,3468)=17.第6页/共23页例2：求(21n+4，14n+3)解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1第7页/共23页6、m0.则（am，bm）=m（a，b）证：由辗转相除法两边同乘m即得。推论1：则证：只要c乘即得。推论2：证：取c=（a，b）即得推论2推论2给出了两个整数的常用设法,即可设第8页/共23页7、若(a,b)=1,则(ac,b)=(c,b)证：(ac,b)|ac,(ac,b)|bc,(ac,b)|(ac,bc)从而有(ac,b)|(a,b)c(a,b)|c又(ac,b)|b,(ac,b)|(b,c)。反之，(c,b)|ac,(c,b)|b(c,b)|(ac,b),注：证明两个最大公因数相等，可用相互整除的方法第9页/共23页8、(a,b)=1,b|acb|c证：因为b|ac,所以(ac,b)=|b|,由7知(ac,b)=(c,b)=|b|,即b|c.9、a|c,b|c,(a,b)=1,ab|c证：由已知有又(a,b)=1,所以有,所以有ab|c.第10页/共23页10、(a,c)=1,(b,c)=1,则有(ab,c)=1证：因为(a,c)=1,由性质7有(ab,c)=(b,c)=1.11、若对i=1，2，.n;j=1,2,m.有,则第11页/共23页证：因为对任意的j有1.第12页/共23页12、设(a,b)=d,则一定存在整数x,y使得ax+by=d证：由辗转相除法倒过来即可得。因为=()a+()b令第一个括号里的数为x,第二个括号里的数为y,即得。第13页/共23页推论：(a,b)=1存在整数x,y使得ax+by=1证：显然。设ax+by=1，又设d=(a,b)，则有d|a,d|b,有d|1,即d=1注:以上给出了证明(a,b)=1的一种常规方法.即先设d=(a,b)，然后证明d|1,即得d=1第14页/共23页下面我们给出n个整数的最大公因数的求法13、为n个整数，又设则有注：性质13说明了n个数的最大公因数可两个两个地求第15页/共23页证：由已知得说明了是的公因数。又设d是的任一公因数，则有又有这说明了是的最大公因数。第16页/共23页例1：若17|2a+3b,试证17|9a+5b证：因为2*(9a+5b)=9(2a+3b)-17b,由已知，有17|2*（9a+5b)因为(17,2)=1,由性质有17|9a+5b.第17页/共23页例2：设k为正奇数，试证证：设,则则有,又所以又有即有9|2s,10|2s,由(9,10)=1,有90|2s.故第18页/共23页例3：设n,a是正整数，试证若不是整数，则一定是无理数.证：若是非整数的有理数，则可设,于是有因为(p,q)=1,所以有,但,所以有所以假设错误，若不是整数，则一定是无理数.注：对任意的正整数n,m有(a,b)=1第19页/共23页介绍两个有名的数-梅森数和费尔马数梅森数：形如2n-1的数叫梅森数，记成Mn=2n-1。费尔马数：n为非负整数，形如的数叫费尔马数，记成Fn=第20页/共23页例4：证明对任意m,n，mn,(Fn,Fm)=1。证：不妨设nm，则Fn-2=(Fn-1-2)Fn-1=Fn-1Fn-2Fm 设（Fn,Fm）=d,则d|Fn,d|Fm d|2但Fn为奇数，d=1,即证。第21页/共23页例5:证明证:设a=bq+r,则=即a,b作转辗相除和 作转辗相除是同步的,即有从而证明了结论.第22页/共23页感谢您的观看！第23页/共23页
