初等数论最大公因数.ppt

《初等数论最大公因数.ppt》由会员分享，可在线阅读，更多相关《初等数论最大公因数.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2 最大公因数,定义1：n( )个不全为零的整数 的公共约数称为 的公约数. 公约数中最大的一个称为 的最大公约数。记成,最大公因数是数论中一个很重要的概念,定义：若 =1，则称 互素。 若对 ,则称 两两互素。 显然两两互素可推出互素，反之不行。 例（2，3，4）=1，但（2，4）=2。 下面主要讨论两个数的最大公因数的性质.,性质： 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的公因子集相同.,证：设d是a，b

2、的任一公因数，则有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） 注：这个性质是后继知识的基础，很重要,因为两个较大的数的最大公因数可转化为较小的两个数的最大公因数,从而为求大公因数找到了方法.,为求两个数的最大公因数，引进辗转相除法,辗转相除法 ：下面的一组带余数除法称为辗转相除法。 设a，b为正整数，依次做带余除法,5、a，b为整数，则（a，b）= 即最后一个不为零的余数 证：由性质4知

3、(a,b)=,推论：a，b的公因数与（a，b）的因数相同。 证：由辗转相除法 d|a，d|b，则有d|（a，b）， 反之也对,例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.,例2：求(21n+4，14n+3) 解：原式=(21n+4,14n+3) =(7n+1,14n+3) =(7n+1,7n+2) =(7n+1,1)=1,6、m0.则（am，bm）=m（a，b） 证：由辗转相除法两边同乘

4、m即得。 推论1： 则 证：只要c乘 即得 。 推论2： 证：取c=（a，b）即得推论2 推论2给出了两个整数的常用设法,即可设,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), 注：证明两个最大公因数相等，可用相互整除的方法,8、(a,b)=1, b|ac b|c,证：因为b|ac, 所以 (ac,b)=|b|, 由7知 (ac,b)=(c,

5、b)=|b|, 即b|c.,9、a|c, b|c, (a,b)=1, ab|c,证：由已知有 又(a,b)=1,所以有 , 所以有 ab|c.,10、(a,c)=1, (b,c)=1, 则有 (a b,c)=1 证：因为(a,c)=1,由性质7有 (a b,c)=(b,c)=1. 11、若对i=1，2，.n; j=1,2,m. 有 ,则,证：因为对任意的j有 1.,12、设(a,b)=d,则一定存在整数x,y使得ax+by=d 证：由辗转相除法倒过来即可得。 因为 =( )a+( )b 令第一个括号里的数为x,第二个括号里的数为y,即得。,推论：(a,b)=1 存在整数x,y使得ax+by=1

6、 证： 显然。 设ax+by=1，又设d=(a,b)， 则有 d|a,d|b,有d|1,即d=1 注:以上给出了证明(a,b)=1的一种常规方法.即先设d=(a,b)，然后证明d|1,即得d=1,下面我们给出n 个整数的最大公因数的求法,13、 为n个整数，又设 则有 注：性质13说明了n个数的最大公因数可两个两个地求,证：由已知得 说明了 是 的公因数。 又设d是 的任一公因数，则有 又有 这说明了 是 的最大公因数。,例1：若17|2a+3b,试证17|9a+5b 证：因为2*(9a+5b)=9(2a+3b)-17b, 由已知，有17|2*（9a+5b) 因为(17,2)=1,由性质有 1

7、7|9a+5b.,例2：设k 为正奇数，试证 证：设 ,则 则有 ,又 所以又有 即有9|2s,10|2s,由(9,10)=1,有90|2s.故,例3：设n,a 是正整数，试证若 不是整数， 则一定是无理数.,证：若 是非整数的有理数，则可设 , , 于是有 因为(p,q)=1,所以有 , 但 ,所以有 所以假设错误，若 不是整数，则一定是无理数.,注：对任意的正整数n,m有(a,b)=1,介绍两个有名的数-梅森数和费尔马数 梅森数：形如2n-1的数叫梅森数，记成Mn=2n-1。 费尔马数：n为非负整数，形如 的数叫费尔马数，记成Fn=,例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, 即证。,例5:证明,证:设a=bq+r,则 = = 即a,b作转辗相除和 作转辗相除是同步的,即有 从而证明了结论.,