Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
221.Podstawowepojęcia
alaia2···akb.Poprzedniwniosekpokazuje,że(ak+i,aia2...ak)l1i,korzystając
zwniosku2,otrzymujemyak+i|bla/aia2···ak.Istniejezatemliczbacałkowitac
taka,żeak+icla/aia2···ak,azatemaia2···akak+icla,tj.aia2···ak+i|a.
7.Znajdowanienajwiększegowspólnegodzielnikaparyliczbpoprzezszukanieich
dzielnikówmożebyć,przywiększychliczbach,czynnościąnaderwyczerpującą.Znacz-
nielepszymsposobemjestmetodaopisanawsiódmejksiędzeElementówEuklidesa,
ztegopowoduznanapodnazwąalgorytmuEuklidesa,którąterazopiszemy.
Jeślia>bsądanymiliczbaminaturalnymi,tozdefiniujemyciągirli,ro,ri,...
orazqi,q2,...wsposóbnastępujący:kładziemyrlila,rolb,ajeślidlapewnego
k≥0mamyjużokreśloneliczbyrli,ro,ri,...,rk,aprzytymrk>0,towyznaczamy
rk+iiqk+iprzez
rklilqk+irk+rk+i
(0≤rk+i<rk).
(1.5)
(Ztwierdzenia1.2(ii)wynika,żewtensposóbliczbyrk+iiqk+isąwyznaczone
jednoznacznie).
Wszczególnościmamyalqib+riiblq2ri+r2.Ponieważciągrijestmalejący,
zatemprzypewnymnotrzymujemyrnli>0,rnl0.
TWIERDZENIE1.7.Jeśliciągrkjestzdefiniowanyprzez(1.5),anjestnajwcześniejszym
indeksem,dlaktóregornl0,to
(a,b)lrnli.
Dowód:Pokażemyprzezindukcję,żernlidzielirjdlajln,nl1,...,1,0,l1.
Wistocie,rnli|0lrnirnli|rnli,ajeślirnlidzielirk+iirk,towobec(1.5)dzieli
takżerkli.Prostaindukcjapokazuje,żernlijestwspólnymdzielnikiemaib,awięc
0<rnli≤(a,b).
Terazpokażemy,że(a,b)dzieliwszystkiewyrazyciągurk.Wistocie(a,b)dzieli
rlilairolb,ajeślidzielirkliirk,towobec(1.5)dzielitakżerk+i.Zatem(a,b)
dzielirnli,coprowadzido(a,b)≤rnliiostatecznieotrzymujemy(a,b)lrnli.
WadąalgorytmuEuklidesajestkoniecznośćwielokrotnegowykonywaniadzielenia
zresztą,codladużychliczbmożebyćczasochłonne.Podamyterazinnysposóbznaj-
dowanianajwiększegowspólnegodzielnika,zaproponowanyw1962r.przezR.Silvera
iJ.Terziana,niemającytejwady.Stosujeonjedynieodejmowanieidzielenieprzez2,
awwieluprzypadkachjestszybszyodalgorytmuEuklidesa.Algorytmtennazywasię
binarnymalgorytmemznajdowanianajwiększegowspólnegodzielnika.
Pomysłjestbardzoprosty:jeśliliczbya,bsąobieparzyste,tozastępujemyaprzez
a/2ibprzezb/2,zapamiętującwspólnyczynnik2;jeżelidokładniejednaztychliczb
jestparzysta,todzielimyjąprzez2,niezmieniającdrugiej.Jeśliwreszcieobiesąniepa-
rzysteiróżne,toodejmujemymniejsząodwiększej,amniejszązostawiamybezzmiany.
Następniepowtarzamyteczynności.Czytelniksprawdzibeztrudu,żeprzytejproce-
durzeiloczyn(a,b)przeziloczynpamiętanychdwójeknieulegazmianie,aponieważ
mniejszazliczbstalesięzmniejsza,więcpopewnymczasiealgorytmmusidoprowa-
dzićdoalblubmin{a,b}l1,cooczywiściewyznaczaszukanynajwiększywspólny
dzielnik.
