1、11.3 1.3 最大公因数与广义欧几里得除法最大公因数与广义欧几里得除法一、最大公因数一、最大公因数 1212,(2),|(1,2,),.1nkna aan nd aknda aa 设设是是个个整整数数 若若整整数数则则称称 是是的的一一个个 定定公公因因数数义义 121212,(,).nnna aaa aaa aa 若若不不全全为为零零,则则整整数数的的所所有有公公因因数数中中最最大大的的一一个个公公因因数数叫叫做做记记作作最最大大公公因因数数.1212,(,)1,nna aaa aa 互互素素特特别别 当当时时 称称或或互互质质.2 1212120,(),;(2)|,|.nnnda aa
2、d|a d|ad|ae a e|ae|ae d 是是的的最最大大公公因因数数1 1 若若则则最最大大公公因因数数可可描描述述为为:(14,21)7,(15,21)3,(14,15,211.1)例例 2,(,)(,).a bb aa b 设设是是两两个个例例整整数数 则则 ,|,3(,).a bb aa bb 设设是是两两个个正正整整数数 如如果果则则例例3 ,|,papapa 设设 是是一一个个素素数数,为为 整整数数 如如果果则则例例与与4 4互互素素.:素素数数与与任任一一整整数数有有如如下下关关系系 ,|.|,|,dpd ap apa 若若则则因因于于是是与与题题设设矛矛盾盾 (,),|
3、,1.p addppdp 证证 设设则则有有因因 是是素素数数 所所以以或或 1,(,)1.dp a故故必必 从从而而4|,|,|(,).dd ab d abda b若若 为为 练练习习奇奇数数，则则5 (1)|,1,|,1.iid aindain证证设设则则有有1212,|,|,|nna aaaaa故故的的公公因因数数也也是是的的公公因因数数.,|,1,|,1.iidaind ain反反之之 设设同同样样有有1212|,|,|,nnaaaa aa故故的的公公因因数数也也是是的的公公因因数数.(2)(1)(2).由由即即得得 1212121212,(),|,|,|;(2)(,)(|,|,|).
4、1nnnnna aana aaaaaa aaaaa 设设是是 个个不不全全为为零零的的整整数数 则则1 1与与的的公公因因数数相相 定定理理同同 6 ,(,)(,)(,)(|,5|).a ba ba babab 设设是是两两个个整整数数 则则例例有有 .2,()bb=b设设 是是任任一一正正整整数数 则则 0,0,定定理理 (0,21)21,(156,0)15,(0,)|.bb例例 0,(0,).bbbb 证证 因因任任何何非非零零整整数数都都是是 的的因因数数 而而正正整整数数的的最最大大因因数数为为故故 7.dd ,.db cdd 所所以以 是是的的公公因因数数 从从而而,.da bdd
5、同同理理可可证证,是是的的公公因因数数 因因而而故故 18591 1573286,1573528614,73例例因因(1859,1573)(1573,286)(286,143)143所所以以 ,(,)(,).a b ca=bq+cqa b=b c设设是是三三个个不不全全为为零零的的整整数数 如如果果其其中中 是是整整数数则则 定定理理3 3 (,),(,),a bdb cdd|a d|b证证 设设则则于于是是|()|,d aq bd c 8二、广义欧几里得除法二、广义欧几里得除法 111,0nnnnnrr qrr 01,.a bra rb设设是是任任意意两两个个正正整整数数 记记反反复复运运用
6、用欧欧几几里里得得除除法法:011221,0,rr qrrr 122332,0,rr qrrr 2111,0,nnnnnnrrqrrr 12110,0.nnnrrrrbnr 因因为为所所以以经经过过有有限限步步骤骤,必必存存在在使使得得9 011223113,(,)(,)(,)(,)(,)(,)(,0)nnnnnna br rr rr rrrr rrr 于于是是由由定定理理 可可知知 ,(,).4nna bra br 设设是是任任意意两两个个正正整整数数是是广广义义欧欧几几里里得得除除法法中中最最后后一一个个 定定理理非非零零余余数数 则则.上上述述求求两两个个整整数数的的最最大大公公因因数数
7、的的方方法法叫叫做做也也叫叫广广义义欧欧几几里里得得除除法法,辗辗转转相相除除法法做做10 1859,81573,(,).aba b 计计算算例例设设 18591 1573286157352862862 143143解解 因因(1859,1573)(1859,1573)143.所所以以 46480,39423,(,).aba b计计算算例例设设9 9解解 法法一一：最最小小非非负负余余数数4648013942370573942357057413811 522122 1 70571413829194138129191219 29192 121948112192481257 48112572242
8、57122433 22463326331267 263757152(46480,39423)1.所所以以 1239423670572919 705722919121929192 1219481 12193481224481222433 224733733572 732122 1法法二二：绝绝对对值值最最小小余余数数464801394237057(46480,39423)1.所所以以 131nnnrr q 0112,rr qr1223,rr qr211,nnnnrrqr在在广广义义欧欧几几里里得得除除法法中中,由由3221,nnnnrrqr211,nnnnrrqr 1322,nnnnrrrq31
9、22,rrr q2011rrr q(,)satba b1232,nnrrr rs t逐逐次次消消去去可可找找到到整整数数使使得得14 1859,1573,(,)1.0abs tsatba b 设设求求整整数数使使得得 例例 18591 1573286157352862862 143143解解 因因(,)143.s=t=sa+tb=a b 所所以以有有整整数数5,6,5,6,使使得得 1573528615735(18591 1573143)于于是是 1573528628618591431 1573 5(1859)6 1573 15 ,(,)0,1,2,5,nnnna bs at ba bnst
10、设设是是任任意意两两个个正正整整数数,则则对对于于这这里里归归 纳纳 定定理理地地定定义义为为 01211012111,0,0,0,jjjjjjjjssssqsttttqt 2,3,jn jq其其中中是是广广义义欧欧几几里里得得除除法法中中的的不不完完全全商商.:0,1,2,jjjjjns at brr 只只需需证证明明 对对于于其其中中 是是广广义义欧欧几几里里得得除除 法法中中分分析析:的的余余数数.(,)nnns at bra b,jn 当当时时 就就有有16 0000001,0,0j=sts at barj 时时,由由题题设设以以及及知知结结论论对对于于成成立立.j对对 作作数数学学归
11、归纳纳法法.1111110,1,1j=sts at bbrj 时时,由由题题设设以以及及知知结结论论对对于于成成立立.11,jjjjks at br假假设设结结论论对对于于成成立立 即即17 211,kkkkjkrrrq 对对于于有有,由由归归纳纳假假设设 可可得得211211()()kkkkkksqsatqtb 21122111()()kkkkkkkkkrrrqsatbsatb qkks at bjk 结结论论对对于于也也成成立立.j由由数数学学归归纳纳法法原原理理,结结论论对对于于所所有有的的 成成立立.18 5,(,)s tsatba b 由由定定理理 及及其其证证明明 可可得得求求整整
12、数数使使得得的的方方法法.010101,1,00,1rarbsstt,首首先先 令令 100(1)0,rsstt 如如果果则则令令.计计算算结结束束19 01201 11,rqrrq rr否否则则,计计算算 211(2)0,rsstt 如如果果则则令令.计计算算结结束束否否则则,计计算算 12312 22,rqrrq rr 201 1201 1,ssq sttq t以以及及 20 11(3)0(3),jjjrjsstt如如果果则则令令否否则则,计计算算 111,jjjjjjjrqrrq rr 211211,jjjjjjjjssqsttqt以以及及 10,nr 最最后后,一一定定有有这这时时,令
13、令 ,nnsstt.计计算算结结束束21jab101100123njq1q2q3qnqjr1jr 1r2r2r3r3r4rnr1nr 1js js2s2s1s3s1ns ns1jt jt1t2t2t3t1nt nt2q 2q :上上述述过过程程可可以以列列表表如如下下|t|s|(,)a b|022 111211211jjjjjjjjjjjjjjjrqrrrq rssqsttqt 1,2,jn 2,3,jn 010101,1,00,1rarbsstt,其其中中23j123456 737,635,)11(abs tsatba b设设计计算算整整数数使使得得例例jqjr1jr 1js js1jt j
14、t63573763510635110210011026230111 2311 410106 6 77233252529 29 31156 56 656530193224|t|s|(,)a b24193737(224)6351 所所以以 5,s t dsatbdda b定定理理 的的逆逆命命题题不不成成立立 即即若若有有整整数数使使 注注:但但 未未必必是是的的最最大大公公因因数数.(,)1,61a bs tsatb存存在在整整数数使使得得定定理理 ,|1,(,)1.d|sa+tbda b=d 所所以以 于于是是因因此此 5.证证 由由性性定定理理要要即即得得必必 (,),|,|,d=a bd
15、a d b充充分分性性 设设则则因因sa+tb=1 125 ,():(1)|,|;(2)|,|,|.abdd=a,bd a d be a e be d 定定 设设，是是任任意意两两个个不不全全为为零零的的整整数数是是正正整整数数 则则的的是是若若则则要要理理充充条条件件7 7 (,),|,|.da bd a d b 证证 若若则则显显然然 5,s tsa+tb=d由由定定理理存存在在整整数数使使得得|,|,|,|.e a e be satbe d 于于是是若若则则因因而而 ,(1),da b反反之之 若若成成立立 则则 是是的的公公因因数数;26 (2),|,|,a be ded 则则若若成成
16、立立的的任任一一公公因因数数于于是是,da b因因此此是是的的最最大大公公因因数数.7(1)(2):定定理理 中中条条件件和和可可以以作作为为最最大大公公因因注注数数的的定定义义.,(1)(,)(,).(,)(2)|,|,(,).|(,)1.(,)(,)abmam bma b ma ba bdd a d bd ddaba ba b 设设，是是任任意意两两个个不不全全为为零零的的整整数数.若若是是任任一一正正整整数数 则则 若若非非零零整整数数 满满足足则则 特特别别地地,定定理理8 827|.ddm于于是是(,),(,),da bdam bm 证证(1)(1)设设则则存存在在整整satbd ,
17、()()ms amt bmdm两两端端同同乘乘以以得得|,|,|,|,d a d bdm am dm bm又又因因|,dm d.mddmd=d而而和和都都是是正正整整数数,所所以以即即(,)(,).a b mma mb,s t数数使使得得28(,)|ab=ddd (2)|,|,(1)d a d b当当时时 由由有有 (,)(|,|)(,)|ababa b=ddddddd (,),(,).|aba bddd 因因此此 ,(,),da b 特特别别地地 取取时时 有有(,)1.(,)(,)aba ba b 29 11200306,23200306,(,)12.aba b计计算算 例例设设(11,2
18、3)200306200306(11,23)1,解解 因因所所以以(,)(11200306,23200306)a b 12,:nna aa个个整整数数的的最最大大公公因因数数的的求求法法 121122233112,0,(,),(,),(,)(,).nnnnnna aanaa addaddada aad 设设是是 个个整整数数,且且令令则则 定定理理9 9 30 (120 150 210 35).计计算算最最大大公公因因数数，例例1313 (120,150)(4,5)3030解解 因因(30,210)30(30,35)5 (120 150 210 35)5.所所以以,最最大大公公因因数数 ，最最后
19、后介介绍绍几几个个与与最最大大公公因因数数有有关关的的结结论论：31 ,2121211.abra babr 设设是是两两个个正正整整数数 若若 被被 除除的的最最小小正正余余数数是是,则则被被除除的的最最小小 引引理理正正余余数数是是1(21)(21)brq,a bq r证证 对对用用欧欧几几里里得得除除法法,存存在在整整数数使使得得 ,1abqrrb2121abq r 于于是是 2 21bqr2(21)(21)rbqr(1)12(21),rb qq 其其中中为为整整数数知知结结论论成成立立.32(,),111.aba ba b 设设是是两两个个正正整整数数,则则2 2和和2 2的的最最 引引
20、理理2 2大大 公公因因数数是是2 2,a b证证 对对用用广广义义欧欧几几里里得得除除法法,得得 1111222123332111,0,0,0,0(,)nnnnnnnnnabqrrbbr qrrbrr qrrbrrqrbrrrarbq 33 11231221112321(21)(21)21(21)(21)21(21)(21)21(21)()21(21)21nnnnnrabrrbrrrrrnrrnrppppp 由由引引理理1 1 1121,nppp 其其中中是是整整数数.(21,21)21nrab 由由广广义义欧欧几几里里得得除除法法知知,34 ,(21 21)1(,)10aba ba b 设设是是两两个个正正整整数数 则则 ,定定理理=1.=1.2证证 由由引引理理 即即得得结结论论.11,21|21|baa bb a设设是是两两个个正正整整数数 则则 定定理理.,0abqrrb证证 设设 121(21)(21),02121abrrbq由由引引理理1 1的的证证明明可可得得351212(2)(2)1).rbqbqq其其中中为为整整数数|b a.r 221|2110ba于于是是 0r
