第四节最大公约数

1、第四节 最大公约数定义 12121212121212,(2),.,(),(,).(,)1,.,.kkkkkkka aa kdda aaa aaa aaa aaa aaa aa整数若整数 是它们之中每一个数的因数那么 就叫做的一个公因数整数的公因数中最大的一个叫做最大公因数 或最大公约数记作若就说互质或互素若中每两个整数互质 就说它们两两互质定理11212(1)(,)(,);(2)( ,1)1,( ,0),( , );(3)( , )( , );(4),( , )1| ;(5),( , )( , ).kka aaaaaaaaa aaa bb apap ap aapbra bb r若 是素数是整数

2、 则或若则12121212121212(1):,|(1,2, ).|(1,2, ),|,|,|.,|,|,|,|,|,|,(,kiikkkkkda aad a ikdaikdaaaaaada aaa aaaaaa a证明 设 是的任一公因数即显然故 也是的一个公因数同理可证的任一公因数也是的一个公因数这样就证得与有相同的公因数因而它们的最大公因数也相同即12,)(,).kkaaaa (2),(3)显然成立;(4):( , ),|,| ,|1,( , )1,| .p add p d ad pdpp ap a证明 设则由得或前者推出后者推出(5):| ,| ,|-.,| ,| ,|.,.( , )

3、( , ).d a d bd ra pbd b d rd apbrabbra bb r证明 若则反之 若则因此 与 的全体公约数的集合就是 与 的全体公约数的集合 这两个集合中最大正整数当然相等定理2111122212111111, 0, 0(1), 0,0( , ).nnnnnnnnnnnna babqrrbbrqrrrrrqrrrrr qrra br若是任意两个正整数则111:(0,)(,)( ,)( , )( , ).nnnnnnrrrrr rr ba b证明定理3,.(1),(,)( , ) ;( , )(2),(,);|(,)1.( , ) ( , )a bmam bma b ma

4、ba ba baba ba b 设是任意两个不为零的整数若 是任一正整数 则若 是的任一公因数 则特别1111222121111:,.1,(,)(,),( , )(,) ,.(1),(), 0(), 0(), 0().2(nnnnnnnnna ba bam bma m b ma b ma b ma bmambm qrmrmbmbmrm qrr mrmrmrm qr mr mrmrmr m qam证明 当有一为零时 定理显然成立今设都不能为零由定理因此不妨假定都是正数在中 把各式两边同乘以即得由定理 得,)( , ) ,.nbmr ma b m因而得证(2):(,)(,)(,)( , )( ,

5、)(,).( , ),(,)1.( , ) ( , )aba ba ba ba ba baba ba ba b 证明成立当时 上式即例题 2141:,.143nnn例 证明 若 是正整数 则是既约分数:,0,( , )( , ):(214,143)(71,143)(71,1)1.214.143abqrrba bb rnnnnnnn证明 由则得是既约分数222,9|,3|( , ).a baabba b例 设是整数 且则222222: 9,9 ()3,3 ()3, 3 () ,3,9 () ,9 3,3,33 .3,3, 3 .3 .3, 3 .3 ( , ).aabbababababababa

6、babababaabbbabaa b证明或若若故( 1859,1573),(30,45,84),(21,2).nn例3求:( 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 解4( , )1,( ,)( , ).m am abm b设则4: ( , )1,( , )( , ( , )( ,)( ,).m am bm b m

7、am bm abm ab证明5( , )1,|,| .m am abm b设那么 若则:4,( , )( ,),| .m bm abmm b5证明 由第 题知6:( ,)( ,( , ) ).m abm m a b证明 注:本题实际上是第4题结论的推广.:( ,( , ) )( ,)( ,).m m a bm mb abm ab6证明思考问题21:(1)(21,21); (2)(2 ,2(1);(3)(, (2); (4)(1,1).ttnnkn k nnnn求最大公因数2:0( , )1,( ,)( , )( , ).ab ca bca b a c证明 若且则5( , )1, |,( , )

8、( , )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证明 若则2:(1)(21,21)(2,21)1;(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时222222: (,)( , ) ,( , )(

9、 , )( ( , ), ( , )(,)(,(,),)(, ( , ),)(, ,)(, ),)( ( ,1),)( ,).am bma b ma b a ca a c b a caac ab bcaac ab bcaa c b bcaa bcaa bca abca bc证明1212123:( ,4)( ,4)2,2| ,2| ,4 |,4 | ,42,42,(,4)(4(),4)4(,1)4.abababakbkabkkkk证明 由可得且可设所以222222222222224:(,)( , ):( , )( , )( , )( , ) ,( , ) )( , )(,)( , )( , ),

10、( , ),( , ),( , )(,)(,).( , , )(,)( ,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 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得证5: ( , )1,( ,)1,( ,)1.|,( , )( ,),( , )( ,),( , )( , )1.a ba abb abc aba ca abb cb abc ac b 证明6:( , ),( ,).| ,| ,|(),|