《初等数论最大公约数学习教案.pptx》由会员分享，可在线阅读，更多相关《初等数论最大公约数学习教案.pptx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1初等初等(chdng)数论数论 最大公约数最大公约数第一页，共33页。12121212121212,(2),.,(),(,).(,)1,.,.kkkkkkka aa kdda aaa aaa aaa aaa aaa aa整数若整数 是它们之中每一个数的因数那么 就叫做的一个公因数整数的公因数中最大的一个叫做最大公因数 或最大公约数记作若就说互质或互素若中每两个整数互质 就说它们两两互质第1页/共33页第二页，共33页。1212(1)(,)(,);(2)( ,1)1,( ,0),( , );(3)( , )( , );(4),( , )1| ;(5),( , )( , ).kka aaa
2、aaaaaa aaa bb apap ap aapbra bb r若 是素数是整数 则或若则第2页/共33页第三页，共33页。12121212121212(1):,|(1,2, ).|(1,2, ),|,|,|.,|,|,|,|,|,|,(,kiikkkkkda aad a ikdaikdaaaaaada aaa aaaaaa a证明 设 是的任一公因数即显然故 也是的一个公因数同理可证的任一公因数也是的一个公因数这样就证得与有相同的公因数因而它们的最大公因数也相同即12,)(,).kkaaaa第3页/共33页第四页，共33页。第4页/共33页第五页，共33页。(4):( , ),|,| ,|
3、1,( , )1,| .p add p d ad pdpp ap a证明 设则由得或前者推出后者推出第5页/共33页第六页，共33页。(5):| ,| ,|-.,| ,| ,|.,.( , )( , ).d a d bd ra pbd b d rd apbrabbra bb r证明 若则反之 若则因此 与 的全体公约数的集合就是 与 的全体公约数的集合 这两个集合中最大正整数当然相等第6页/共33页第七页，共33页。111122212111111, 0, 0(1), 0,0( , ).nnnnnnnnnnnna babqrrbbrqrrrrrqrrrrr qrra br若是任意两个正整数则第7
4、页/共33页第八页，共33页。111:(0,)(,)( ,)( , )( , ).nnnnnnrrrrr rr ba b证明第8页/共33页第九页，共33页。,.(1),(,)( , ) ;( , )(2),(,);|(,)1.( , ) ( , )a bmam bma b ma ba ba baba ba b 设是任意两个不为零的整数若 是任一正整数 则若 是的任一公因数 则特别第9页/共33页第十页，共33页。1111222121111:,.1,(,)(,),( , )(,) ,.(1),(), 0(), 0(), 0().2(nnnnnnnnna ba bam bma m b ma b
5、ma b ma bmambm qrmrmbmbmrm qrr mrmrmrm qr mr mrmrmr m qam证明 当有一为零时 定理显然成立今设都不能为零由定理因此不妨假定都是正数在中 把各式两边同乘以即得由定理 得,)( , ) ,.nbmr ma b m因而得证第10页/共33页第十一页，共33页。(2):(,)(,)(,)( , )( , )(,).( , ),(,)1.( , ) ( , )aba ba ba ba ba baba ba ba b 证明成立当时 上式即第11页/共33页第十二页，共33页。2141:,.143nnn例 证明 若 是正整数 则是既约分数第12页/共3
6、3页第十三页，共33页。:,0,( , )( , ):(214,143)(71,143)(71,1)1.214.143abqrrba bb rnnnnnnn证明 由则得是既约分数第13页/共33页第十四页，共33页。222,9|,3|( , ).a baabba b例 设是整数 且则第14页/共33页第十五页，共33页。222222: 9,9 ()3,3 ()3, 3 () ,3,9 () ,9 3,3,33 .3,3, 3 .3 .3, 3 .3 ( , ).aabbababababababababababaabbbabaa b证明或若若故第15页/共33页第十六页，共33页。( 1859,
7、1573),(30,45,84),(21,2).nn例3求第16页/共33页第十七页，共33页。:( 1859,1573)(1859,1573)(286,1573)(286,1573286 5)(286,143)(0,143)143;(30,45,84)(30,15,84)(0,15,84)(15,84)(15, 6)(3, 6)3;(21,2)(21 2(2),2)(3,2)332.13 ,31nnnnnnnknkk 解第17页/共33页第十八页，共33页。4( , )1,( ,)( , ).m am abm b设则第18页/共33页第十九页，共33页。4: ( , )1,( , )( ,
8、( , )( ,)( ,).m am bm b m am bm abm ab证明第19页/共33页第二十页，共33页。5( , )1,|,| .m am abm b设那么 若则第20页/共33页第二十一页，共33页。:4,( , )( ,),| .m bm abmm b5证明 由第 题知第21页/共33页第二十二页，共33页。6:( ,)( ,( , ) ).m abm m a b证明第22页/共33页第二十三页，共33页。:( ,( , ) )( ,)( ,).m m a bm mb abm ab6证明第23页/共33页第二十四页，共33页。21:(1)(21,21); (2)(2 ,2(1
9、);(3)(, (2); (4)(1,1).ttnnkn k nnnn求最大公因数2:0( , )1,( ,)( , )( , ).ab ca bca b a c证明 若且则第24页/共33页第二十五页，共33页。5( , )1, |,( , )( , )1.a bc abc ac b若则6,0,( , )( ,).a ba ba bka若不全为 则4:( , , )(,)( , )( , )( , ).a b c ab bc caa b b c c a证明3:( ,4)( ,4)2,(,4)4.abab证明 若则第25页/共33页第二十六页，共33页。2:(1)(21,21)(2,21)1;
10、(2)(2 ,2(1)(2 ,2)2;2(3)(, (2)(,2 )( ,2);(4)(1,1)(1,21)(1,3)3.tttnnnk nkn k nknkk nknnnnnnn1解是偶数是奇数当n=3k+1时1 当n=3k,3k+2时第26页/共33页第二十七页，共33页。222222: (,)( , ) ,( , )( , )( ( , ), ( , )(,)(,(,),)(, ( , ),)(, ,)(, ),)( ( ,1),)( ,).am bma b ma b a ca a c b a caac ab bcaac ab bcaa c b bcaa bcaa bca abca bc
11、证明第27页/共33页第二十八页，共33页。1212123:( ,4)( ,4)2,2| ,2| ,4 |,4 | ,42,42,(,4)(4(),4)4(,1)4.abababakbkabkkkk证明 由可得且可设所以第28页/共33页第二十九页，共33页。222222222222224:(,)( , ):( , )( , )( , )( , ) ,( , ) )( , )(,)( , )( , ),( , ),( , ),( , )(,)(,).( , , )(,)( ,am bma b ma b b c c aa b b a b c c aab b ac bc c aab c a b c
12、 a ac c a bc c aabc a b b c b a aca c bcabcabc a b b c b a aca c bca b c ab bc caab a b证明 由得222222222222222222, ),( , , ),( , , )(,),(,),(,)(,)(,).c bc a b c ca a b ca b ab abcabc b c bca c abc aca b ab abc abc b c bca c abc aca b ab b c bca c abc ac得证第29页/共33页第三十页，共33页。5: ( , )1,( ,)1,( ,)1.|,( , )( ,),( , )( ,),( , )( , )1.a ba abb abc aba ca abb cb abc ac b 证明第30页/共33页第三十一页，共33页。6:( , ),( ,).| ,| ,|(),|.| ,.a bda bkadd a d bdbkad dddd ddd证明 设因为所以即同样可证而均为正数 故第31页/共33页第三十二页，共33页。3.( , )1,:(,)12.a bab ab设证明或4.:( ,)|( , )( , ).a uva u a v证明第32页/共33页第三十三页，共33页。