初等数论最大公因数实用教案

1、定义：若 =1，则称 互素。 若对 ,则称 两两互素。显然两两互素可推出互素，反之不行。例（2，3，4）=1，但（2，4）=2。下面主要讨论(toln)两个数的最大公因数的性质.),(21naaanaaa,211),(,jiaaji有naaa,21第1页/共23页第一页，共24页。性质：1、 =2、(0,b)=|b|, b0.3、(a,b)=(b,a) 前3条比较简单.4、若a=bq+c，则（a，b）=（b，c）分析(fnx): (1)可证(a,b) 和(b,c)相互整除.(2)利用集合知识说明a,b和b,c的公因子集相同.),(21naaa|)|,| |,(|21naaa第2页/共23页第二

2、页，共24页。证：设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）注：这个性质(xngzh)是后继知识的基础，很重要,因为两个较大的数的最大公因数可转化为较小的两个数的最大公因数,从而为求大公因数找到了方法.第3页/共23页第三页，共24页。为求两个(lin )数的最大公因数，引进辗转相除法辗转相除法 ：下面的一组带余数(ysh)除法称为辗转相除法。 设a，b为正

3、整数，依次做带余除法,11rbqa,221rqrbnnnnrqrr12br 10120rr 10nnrr111nnnnrqrr01nr第4页/共23页第四页，共24页。5、a，b为整数，则（a，b）= 即最后(zuhu)一个不为零的余数证：由性质4知(a,b)=nrnnnnrrrrrrrb)0 ,(),(),(),(1211推论(tuln)：a，b的公因数与（a，b）的因数相同。证：由辗转相除法 d|a，d|b，则有d|（a，b）， 反之也对第5页/共23页第五页，共24页。例1、 求24871与3468的最大公因数解： 24871=3468*7+595，3468=595*5+493，595=

4、493*1+102，493=102*4+85，102=85*1+17，85=17*5,所以(suy)(24871,3468)=17.第6页/共23页第六页，共24页。例2：求(21n+4，14n+3)解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1第7页/共23页第七页，共24页。6、m0.则（am，bm）=m（a，b）证：由辗转相除法两边同乘m即得。推论1： 则 证：只要c乘 即得 。推论2：证：取c=（a，b）即得推论2推论2给出了两个整数的常用(chn yn)设法,即可设,|,|, 0bcacc cbacbca),(),(1),

5、(),(),(babbaa),(cbcacba),(1),(),(,1111babaddbbdaa第8页/共23页第八页，共24页。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),注：证明两个最大公因数相等，可用相互整除(zhngch)的方法第9页/共23页第九页，共24页。8、(a,b)=1, b|ac b|c证：因为(yn wi)b|ac, 所

6、以 (ac,b)=|b|, 由7知 (ac,b)=(c,b)=|b|, 即b|c.9、a|c, b|c, (a,b)=1, ab|c 证：由已知有 又(a,b)=1,所以(suy)有 ,所以(suy)有 ab|c.2121,bcacbccacc2|bca2|ca32acc 32abcbcc 第10页/共23页第十页，共24页。10、(a,c)=1, (b,c)=1, 则有 (a b,c)=1证：因为(yn wi)(a,c)=1,由性质7有 (a b,c)=(b,c)=1.11、若对i=1，2，.n; j=1,2,m. 有 ,则1),(11mjjniiba1),(jibaji有第11页/共23页

7、第十一页，共24页。证：因为(yn wi)对任意的j有 1.1),),(),(221jnjnjnbabaabaaa（),(),(222121mnmnbbaabbbaaa),21mnbaaa （第12页/共23页第十二页，共24页。12、设(a,b)=d,则一定存在整数x,y使得ax+by=d证：由辗转(zhnzhun)相除法倒过来即可得。 因为 =( )a+( )b令第一个括号里的数为x,第二个括号里的数为y,即得。21nnnnrrqrd第13页/共23页第十三页，共24页。推论：(a,b)=1 存在整数(zhngsh)x,y使得ax+by=1 证： 显然。 设ax+by=1，又设d=(a,b

8、)，则有 d|a,d|b,有d|1,即d=1注:以上给出了证明(a,b)=1的一种常规方法.即先设d=(a,b)，然后证明d|1,即得d=1第14页/共23页第十四页，共24页。下面我们(w men)给出n 个整数的最大公因数的求法13、 为n个整数(zhngsh)，又设 则有注：性质13说明了n个数的最大公因数可两个两个地求naaa,21nnndaddaddaa),(),( ,),(1332221),(21naaand第15页/共23页第十五页，共24页。证：由已知得 说明(shumng)了 是 的公因数。 又设d是 的任一公因数，则有 又有 这说明(shumng)了 是 的最大公因数。ni

9、adadddiniiii，2 , 1,|,|,|1ndnaaa,21naaa,21,|,|221ddadad,|33ddadndnaaa,21ndd|第16页/共23页第十六页，共24页。例1：若17|2a+3b,试证17|9a+5b证：因为(yn wi)2*(9a+5b)=9(2a+3b)-17b, 由已知，有17|2*（9a+5b) 因为(yn wi)(17,2)=1,由性质有 17|9a+5b.第17页/共23页第十七页，共24页。例2：设k 为正奇数(j sh)，试证证：设 ,则则有 ,又所以又有 即有9|2s,10|2s,由(9,10)=1,有90|2s.故 kkk921 |921k

10、kks921)19()82()91 (2kkkkkks)09()81 (90(2kkkkkks）292Ns kkk921 |9211102Ns 第18页/共23页第十八页，共24页。例3：设n,a 是正整数(zhngsh)，试证若 不是整数(zhngsh)， 则一定是无理数.na证：若 是非(shfi)整数的有理数，则可设 , , 于是有因为(p,q)=1,所以有 , 但 ,所以有 所以假设错误，若 不是整数，则一定是无理数.qpan1),( , 1qpqnannqpa 1),(nnqp1nqnpnqna注：对任意(rny)的正整数n,m有(a,b)=11),(mnba第19页/共23页第十九

11、页，共24页。介绍两个有名(yu mng)的数-梅森数和费尔马数梅森数：形如2n-1的数叫梅森数，记成Mn=2n-1。费尔马数：n为非负整数，形如 的数叫费尔马数，记成Fn= 122n122n第20页/共23页第二十页，共24页。例4： 证明对任意(rny) 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, 即证。) 12)(12(1122nn01FF第21页/共23页第二十一页，共24页。例5:证明(zhngmng)证:设a=bq+r,则=即a,b作转辗相除和 作转辗相除是同步(tngb)的,即有从而证明了结论.12),(),(babaMM1222)2(12rrrqbrbqaM12) 12(12) 12(21rbrbrNN12) 12(1nnrrNbaMM ,12),(),(),(),(1barrrbbannMMMMMM第22页/共23页第二十二页，共24页。感谢您的观看(gunk