Một thuật toán nổi tiếng Euclide

Để đưa ra được thuật toán, trước hết Euclide nhận xét:Giả sử f và g không đồng thời bằng không là 2 số nguyên không âm và f = g. Khi đó:Nếug=0 thì USCLN(f,g)=f.Nếug ≠ 0 thì ta có hệ thức USCLN(f,g)=USCLN(g,r) với r là số dư trong phép chia của f chog.Các bạn có thể hoàn toàn chứng minh được kết luận trên, chỉ cần lưu ý rằng với mọi a, cácsố f và g có ước số chung giống hệt các ước số chung của g và fag.Trong khi đó, số dư rcũng có dạng fag....
Nội dung trích xuất từ tài liệu:
Một thuật toán nổi tiếng Euclide Một thuật toán nổi tiếng EuclideThuậttoánEuclideĐểđưarađượcthuậttoán,trướchếtEuclidenhậnxét:Giảsửfvàgkhôngđồngthờibằngkhônglà2sốnguyênkhôngâmvàf>=g.Khiđó:Nếug=0thìUSCLN(f,g)=f.Nếug≠0thìtacóhệthứcUSCLN(f,g)=USCLN(g,r)vớirlàsốdưtrongphépchiacủafchog.Cácbạncóthểhoàntoànchứngminhđượckếtluậntrên,chỉcầnlưuýrằngvớimọia,cácsốfvàgcóướcsốchunggiốnghệtcácướcsốchungcủagvàfag.Trongkhiđó,sốdưrcũngcódạngfag.Từnhữngnhậnxéttrên,EuclideđãđưarathuậttoánsauđểtìmUSCLNcủahaisốnguyênkhôngâm:Cho2sốnguyênkhôngâm,đểtìmUSCLNcủachúngtathựchiệncácbướcsau:Bước1:Sosánhsốthứhaivới0.Nếusốthứhaibằng0thìdừnglại,kếtluậnUSCLNchínhlàsốthứnhất.Nếusốthứhaikhác0thìtínhsốdưtrongphépchiasốthứnhấtchosốthứhai.Chuyểnsangbước2.Bước2:Thaysốthứnhấtbằngsốthứhai,sốthứhaibằngsốdưvừatínhđược,rồiquaylạibước1.Cácbạnlưuý:Sốdưluônbéhơnsốchia,vàmộtdãygiảmcácsốnguyênkhôngâmkhôngthểvôhạn.Dođó,thuậttoánEuclidechắcchắnsẽdừngtạimộtbướcnàođó,khisốdưbằng0.Vídụ:TìmUSCLN(39,15).ápdụngthuậttoánnày,tađượccáccặpsốcóthứtự:(39,15),(15,9),(9,6),(6,3),(3,0).NhưvậycuốicùngtathuđượcUSCLN(39,15)=3.TínhưuviệtcủathuậttoánEuclideTrongthựctiễntínhtoán,đaphầncácthuậttoáncổdầnbịthaythếbởicácthuậttoánmới.ThuậttoánEuclidethoátkhỏisốphậnđótrướchếtlànhờtínhtiếtkiệmcủanó.GiátrịUSCLN(f,g)cóthểtínhđượctheonhiềucáchkhácnhau,vídụcóthểtínhtheothuậttoántựnhiênnhưsau:Nếug=0thìlấyUSCLN(f,g)=f,nếukhôngthìchọntrongdãysốg,g1,g2,...,1sốđầutiênmàphépchiacủafvàgchosốđócùngchosốdưlà0.Nhưngcũngnhưcácthuậttoánkhác,thuậttoánnàyquálãngphí.Chẳnghạntrongtrườnghợpfvàgnguyêntốcùngnhau,nóyêucầutới2gphépchia.BâygiờtasẽđinghiêncứusốphépchiamàthuậttoánEuclideyêucầuvàchỉrarằngvớigđủlớnthìnónhỏhơnhẳn2g.TasẽxétdãycácsốdưthuđượctrongquátrìnhthựchiệnthuậttoánEuclide.Đểthuậntiện,takíhiệuf0=f,f1=g(vàgiảsửf0>f1).Cácsốdưthuđượcsẽkíhiệulầnlượtlàf2,f3,...,fn,cònthươngsốcủacácphépchiaf0chof1,f1chof2,...,fn1chofnsẽkíhiệulàa1,a2,...,an:f0=a1f1+f2,f1=a2f2+f3,...(1)fn2=an1fn1+fn,fn1=anfn,trongđó,USCLN(f,g)=fn.Sốdưluônbéhơnsốchianênf0>f1>f2>...>fn>0.Từđósuyracácthươngsốa1,a2,...,anluônlớnhơnhoặcbằng1.Bổđề1.Vớii=1,2,...,n2taluôncófi>2fi+2.Chứngminh.fi=ai+1fi+1+fi+2>=fi+1+fi+2>2fi+2.Bổđề2.GiảsửklàmộtsốtựnhiênsaochothuậttoánEuclideápdụngcho2sốf0,f1khôngdừngsau2kphépchia(tứclàf2k+1>=1).Khiđóf1>2k.Chứngminh.Ápdụngbổđề1,tathuđượcf1>2f3>4f5>...>2kf2k+1>=2k.Địnhlí.SốphépchiamàthuậttoánEuclideyêucầukhôngvượtquá2[log2f1]+2.([x]làkíhiệuphầnnguyêncủax).Chứngminh.Từbổđề2tasuyranếuklàsốtựnhiênsaochof1MộtưuthếnữacủathuậttoánEuclidelànócónhiềucáchmởrộngvàtổngquát.Mộtthuậttoánthườnggặplàthuậttoántínhcácsốnguyênu,vsaochofu+gv=USCLN(f,g)(2)Nócũngchínhlàcáchgiảiphươngtrìnhkx+ly=m,vớik,l,mlàcácsốnguyênsaochok,lkhôngđồngthờibằng0,cònmchiahếtchoUSCLN(|k|,|l|).Giảsử|k|u+|l|v=d,khiđó|k|um/d+|l|vm/d=m,suyrak(c1um/d)+l(c2vm/d)=mvớicj= 1,j=1,2.Thuậttoántìmu,vthoảmãn(2)nhưsau:Kíhiệuf0=f,f1=gvàxét(1).Giảsửvớisối>=n2nàođó,tađãbiếtfi,fi+1vàcácthừasốp,q,s,ttươngứngsaochof0p+f1q=fi,f0s+f1t=fi+1(4)Khiđóchiafichofi+1tanhậnđượcthươngsốai+1vàsốdưfi+2,tacóthểtínhđượcthừasốứngvớifi+2:vìfiai+1fi+1=fi+2nênsửdụnghệthức(4)chofi,fi+1tathuđượcf0(pai+1s)+f1(qai+1t)=fi+2.Nhưvậy,đểgiảibàitoán(2),taápdụngthuậttoánEuclidecho2sốfvàg,đồngthờiởmỗibướcngoài2giátrịnhưtrước,taphảixemxétcácthừasốp,qvàs,ttươngứngvớichúng.ởbướcđầutiên,cácthừasốtươngứngvớif,gtasẽlấylà1,0và0,1.Saukhithựchiệnphépchiavànhậnđượcthươngsốacùngsốdư,taphảixétsốdư:nếusốdưkhác0,trướckhichuyểnsangbướcsau,taphảitínhcácthừasốtươngứngvớisốdưnhậnđượctheocôngthứcpasvàqat.sốdưkhác0cuốicùngvàcácthừasốuvàvtươngứngvớinósẽthoảmãn(2).Trongquátrìnhápdụngthuậttoántrênvớif=39vàg=15tathuđượcdãycácsốdưlầnlượtlà9,6,3,0vàcácthừasốtươngứngvới3sốdưđầulà1,2;1,3;2,5.Nhưvậy,39.2+15.(5)=3=USCLN(39,15).Bâygiờtanhậnthấyrằng,thuậttoáncóthểbiếnđổisaochosốcácthaotácmànóyêucầugiảmđigầnmộtlầnrưỡi:từ2sốuvàvtachỉcầntínhv,sauđóxácđịnhutheocôngthứcu=(USCLN(f,g)gv)/f.Vớif=39,g=15tacóthểđặtu=(315.(5))/39=2.Dãycácphépchiacódưtheosơđồ(1)cũnglàcơsởcủacủathuậttoánliênphânsố,chophépthuđượcmộtxấpxỉrấtthúvịcủaphânsốf0/f1.Liênphânsố(hữuhạn)làbiểuthứcdạng:(5)trongđób1,b2,...,bklàcácsốtựnhiên.Liênphânsố(5)thườngkíhiệungắngọnlà[b1,b2,...,bk].Vìf0=a1f1+f2,nêntacó:Tiếptheo,cũngbằngcáchnhưvậy,tasẽbiếnđổif2,...Cuốicùngtathuđượcf1/f0=[a1,a2,...,an].Xétthêmcácliênphânsố[a1],[a1,a2],...,[a1,a2,...,an1],giátrịcủachúngđượcgọilàcácphânsốthíchhợpcủaf1/f2.Kíhiệudạngtốigiảncủacácphânsốthíchhợpbằngp1/q1,p2/q2,.. ...