初等數(shù)論第一章第4節(jié) 最大公約數(shù)

1、第四節(jié) 最大公約數(shù)定義 12121212121212,(2),.,(),(,).(,)1,.,.kkkkkkka aa kdda aaa aaa aaa aaa aaa aa整數(shù)若整數(shù) 是它們之中每一個數(shù)的因數(shù)那么 就叫做的一個公因數(shù)整數(shù)的公因數(shù)中最大的一個叫做最大公因數(shù) 或最大公約數(shù)記作若就說互質(zhì)或互素若中每兩個整數(shù)互質(zhì) 就說它們兩兩互質(zhì)定理11212(1)(,)(,);(2)( ,1)1,( ,0),( , );(3)( , )( , );(4),( , )1| ;(5),( , )( , ).kka aaaaaaaaa aaa bb apap ap aapbra bb r若 是素數(shù)是整數(shù)

2、 則或若則12121212121212(1):,|(1,2, ).|(1,2, ),|,|,|.,|,|,|,|,|,|,(,kiikkkkkda aad a ikdaikdaaaaaada aaa aaaaaa a證明 設(shè) 是的任一公因數(shù)即顯然故 也是的一個公因數(shù)同理可證的任一公因數(shù)也是的一個公因數(shù)這樣就證得與有相同的公因數(shù)因而它們的最大公因數(shù)也相同即12,)(,).kkaaaa (2),(3)顯然成立;(4):( , ),|,| ,|1,( , )1,| .p add p d ad pdpp ap a證明 設(shè)則由得或前者推出后者推出(5):| ,| ,|-.,| ,| ,|.,.( , )

3、( , ).d a d bd ra pbd b d rd apbrabbra bb r證明 若則反之 若則因此 與 的全體公約數(shù)的集合就是 與 的全體公約數(shù)的集合 這兩個集合中最大正整數(shù)當(dāng)然相等定理2111122212111111, 0, 0(1), 0,0( , ).nnnnnnnnnnnna babqrrbbrqrrrrrqrrrrr qrra br若是任意兩個正整數(shù)則111:(0,)(,)( ,)( , )( , ).nnnnnnrrrrr rr ba b證明定理3,.(1),(,)( , ) ;( , )(2),(,);|(,)1.( , ) ( , )a bmam bma b ma

4、ba ba baba ba b 設(shè)是任意兩個不為零的整數(shù)若 是任一正整數(shù) 則若 是的任一公因數(shù) 則特別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證明 當(dāng)有一為零時 定理顯然成立今設(shè)都不能為零由定理因此不妨假定都是正數(shù)在中 把各式兩邊同乘以即得由定理 得,)( , ) ,.nbmr ma b m因而得證(2):(,)(,)(,)( , )( ,

5、)(,).( , ),(,)1.( , ) ( , )aba ba ba ba ba baba ba ba b 證明成立當(dāng)時 上式即例題 2141:,.143nnn例 證明 若 是正整數(shù) 則是既約分?jǐn)?shù):,0,( , )( , ):(214,143)(71,143)(71,1)1.214.143abqrrba bb rnnnnnnn證明 由則得是既約分?jǐn)?shù)222,9|,3|( , ).a baabba b例 設(shè)是整數(shù) 且則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設(shè)則4: ( , )1,( , )( , ( , )( ,)( ,).m am bm b m

7、am bm abm ab證明5( , )1,|,| .m am abm b設(shè)那么 若則:4,( , )( ,),| .m bm abmm b5證明 由第 題知6:( ,)( ,( , ) ).m abm m a b證明 注:本題實際上是第4題結(jié)論的推廣.:( ,( , ) )( ,)( ,).m m a bm mb abm ab6證明思考問題21:(1)(21,21); (2)(2 ,2(1);(3)(, (2); (4)(1,1).ttnnkn k nnnn求最大公因數(shù)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解是偶數(shù)是奇數(shù)當(dāng)n=3k+1時1 當(dāng)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證明 由可得且可設(shè)所以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:( , ),( ,).| ,| ,|(),|