i
i
“1169-Juvan-0” — 2010/7/19 — 11:34 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 21 (1993/1994)
Številka 2
Strani 116–121
Martin Juvan:
O EVKLIDOVEM ALGORITMU
Ključne besede: računalništvo, matematika, teorija števil, Evklidov al-
goritem.
Elektronska verzija: http://www.presek.si/21/1169-Juvan-Evklid.pdf
c© 1993 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
o EVKLIDOVEM AlGORITMU
Pri reševanju različnih problemov se večkrat srečamo z iskanjem najvecjega
skupnega delitelja dveh naravnih ali včasih dveh celih števil. Da bomo problem
dobro razumeli, si najprej oglejmo natančne definicije obravnavanih pojmov.
Pravimo , da celo število a deli celo štev ilo b , če obstaja tako celo število k, da
je b = ka . 5tevilu a pravimo tudi delitelj števila b. Tako na primer 5 deli 235.
saj je 235 = 5 · 47. medtem ko 7 ne deli 235 , saj 2~5 ni celo število . Prejšnji
trditvi krajše zapišemo tudi takole: 5 I 235 in 7 A235. Neposredno iz definicije
sledi, da imata števili ain -a enake delitelje. Ker je po definiciji kvocient med
številom in vsakim njegovim deliteljem celo število , so vsi delitelji neničelnega
celega števila a zajeti med števi li -lal. -lal + 1, . . . , lal- 1, lal . Izjema je le
število O, ki je deljivo z vsakim celim štev ilom, saj je O= O· a za vsako celo
število a.
5tevilu d , ki deli celi števili a in b, pravimo skupni delitelj števil ain b.
Ker ima po gornjem razmisleku vsako neni čelno celo število le končno mnogo
deliteljev, imata poljubni različni celi števili a in b le končno mnogo skupn ih
deliteljev (saj je vsaj eno od obeh števil razli čno od nič) . Ker pa vsaka
končna neprazna množ ica celih števil vsebuje največje število , obstaja tudi
največje štev ilo v (neprazni . saj števili 1 in -1 delita vsako drugo celo število)
množici skupnih deliteljev števil a in b . To število imenujemo največji skupni
delitelj števil a in b. V računalniških krogih (v katerih prevladuje angleško
izrazoslovje) se je za največji skupni delitelj štev il a in b uveljavila pisava
gcd(a , b). To je kratica za izraz greatest common divisor, ki v angleščini
pomeni največji skupni delitelj .
Končajmo z definicijami in poglejmo, kako izračunamo največj i skupni
delitelj dveh števil. Vzemimo poljubni naravni števili a in b ter ju razstavimo
na prafaktorje:
ln b - p{3t p{3k- 1 . . . k
kjer so PI •. .. , Pk vsa različna praštev ila, ki nastopajo v razcepu števila a, v
razcepu števila b ali pa v razcepu obeh, eksponenti cq . . . . . Ct.k in f31 . . . . ,f3k
pa so naravna števila ali število O. Vrednost Omoramo v takem zapisu dovoliti ,
saj nekateri prafaktorji lahko nastopajo le v razcepu enega od števil a ali b.
Ponovimo, da je aD = 1 za vsako celo število a . Tako imamo
I 117
Največji skupni delitelj števil a in b potem lahko zap išemo v obliki
d( b) min{a1ol3d min{ad3dgc a, = PI . . . Pk
V zgornjem primeru je torej
Vendar pa največjega skupnega delitelja dveh števil običajno ne iščemo
tako, da obe števil i razstavimo in izberemo skupne prafaktorje z ustreznimi
eksponenti , ampak si raje pomagamo z Evklidovim algoritmom . Kot nam
pove njegovo ime, so ga poznali že stari Grki. Omenjen je v sedmi knjigi
Evklidovih Elementov. Algoritem temelji na naslednjih preprostih dejstvih :
- Za vsako naravno število aje gcd(a, O) = a.
- Naj bo a = kb + r, kjer je O:s r < b . ~tevilo a torej delimo z naravnim
številom b , s k označimo celoštevilski kvocient , z r pa ostanek pri tem
deljenju. Potem je gcd(a, b) = gcd(b, r).
O veljavnosti prve trditve smo se že prepričali . Skicirajmo še dokaz druge .
Pokazali bomo, da so skupni delitelji števil a in b ravno skupn i delitelj i števil
b in r. Potem pa bo tudi največj i skupni delitelj v obeh primerih enak. Naj
bo d skupni delitelj števil a in b, torej je a = kI d in b = k2d . Ker pa je
r = a - kb = (kI - k k2)d , število d deli tud i število r . Dokaz , da je vsak
skupni delitelj števil b in r tudi skupni delitelj števil a in b, je skoraj enak,
zato ga prepuščam bralcu.
Iskanje največjega skupnega delitelja z Evklidovim algoritmom ilustriraj-
mo na zgornjem primeru:
882 = 3 . 270 + 72
270 = 3 · 72 + 54
72 = 1 ·54 + 18
54 = 3 ·18 + O
Največji skupni delitelj števil 882 in 72 je tako zadnji neničelni ostanek, v
našem zgledu je to seveda število 18.
Z nekaj znanja programiranja lahko Evklidov algoritem zapišemo kot
kratek funkcijski podprogram v programskem jeziku pascal.
{ Izrsčunsmo novi ostanek. }
{ Prejšnje drugo število postane novo prvo stevilo. }
{ Novi ostanek postane drugo število . }
118
function GCD(a,b: integer): integer;
{ lzrečune nsjve čji skupni delitelj števi! a
var
r: integer;
begin
while b<>O do begin
r:=a mod b;
a:=b;
b .eer:
end ;
GCD:=abs(a);
end; {GCO}
ln b z Evklidovim algoritmom. }
I
V rešitvi smo uporabili tudi v pascal vgrajeno funkcijo mod . Ta je tesno
povezana s funkcijo div, ki jo bomo potrebovali kasneje . Klic a mod b
vrne ostanek pri deljenju števila a s številom b. Predznak ostanka je enak
predznaku števila a. Klic a div b vrne celoštevilski kvocient števil a in b.
Kvocient je pozitiven , če imata števili a in b enak predznak, sicer pa je
negativen . Na primer:
5 mod 3 = 5 mod -3 = 2 in -5 mod 3 = -5 mod -3 = -2 ,
5 div 3 = -5 div -3 = 1 in 5 div -3 = -5 div 3 = -l .
Obe operaciji povezuje zveza a = (a div b) . b + a mod b, ki velja za vsa
cela števila .
Gornji algoritem je tudi zelo robusten. Za pravilno delovanje ni potreb-
no, da je število a po absolutni vrednosti večje od števila b. te je število
b večje , potem prva ponovitev zanke while poskrbi za zamenjavo vrednosti
obeh spremenljivk . Prav tako ni nujno, da sta vrednosti obeh parametrov
nenegativni. te sta obe števili negativni, račun poteka enako kot pri pozitivnih
podatkih . le da so tudi vsi ostanki negativni. Ker pa je rezultat funkcije GCD
absolutna vrednost zadnjega neničelnega ostanka, ti predznaki ne vplivajo na
končni rezultat. te pa sta vhodna podatka različno predznačena, se tudi
predznaki ostankov v algoritmu izmenjujejo.
Gornji podprogram lahko sprogramiramo tudi rekurzivno.
function GCDr(a,b: integer) : integer;
{Rekurzivni Evklidov algoritem. }
begin
if b=O then
GCDr:=abs(a)
else
GCDr:=GCDr(b,a mod bl;
end; {GCOr}
119
Rekurzivna rešitev je elegantnejša, saj je skoraj dobesedno enaka mate-
matičnemu opisu algoritma s prejšnje strani . Seveda pa ima tudi svoje sla-
bosti. Tako vsak rekurzivni klic porabi nekaj dodatnega prostora in časa za
oba parametra in " knj igovodstvo" ob klicu. Poskusi pokažejo , da je gornji
rekurzivn i podprogram približno dvakrat počasnejši od ite rat ivnega .
ln za kaj lahko uporabimo izračunani največji skupni delitelj? Recimo pri
reševanju linearne diofantske enačbe z dvema neznankama . Tudi take ena čb e
so reševali že v antiki, svoje ime pa so dobile po matematiku Diofantu, ki
je živel okoli leta 250. Teorija pravi, da je pri izbranih celih številih a, b in
c enačba ax + by = c rešljiva v celih številih natanko tedaj, ko gcd( a, b)
deli c . In kako v tem primeru poiščemo kakšno rešitev? Pokazal i bomo , da si
tudi tu lahko pomagamo z Evklidovim algoritmom . Z njegovo pomočjo bomo
poiskali taki celi števili Xo in Yo, da bo veljalo
axo+ byo = gcd(a,b).
Oglejmo si postopek na prejšnjem primeru . Zadnji neničelni ostanek želimo
zapisati kot celoštevilsko kombinacijo začetn ih števil a in b . To dosežemo
z zaporednim izražanjern ostankov od zadnjega proti prvemu in vstavljanjem
dobljene zveze v prejšnjo vrstico Evklidove sheme. Tako imamo:
18 = 72 - 54
72 - (270 - 3 . 72)
-270 + 4 ·72
-270 + 4 · (882 - 3 . 270)
= 4 . 882 - 13 . 270
54 = 270 - 3 . 72
72 =882 - 3 . 270
Vzamemo Xo = 4 in yo = -13 in naloga je rešena .
Vendar pa je računanje s svinčn ikom in papi rjem naporno ln zamud-
no, pa tudi napake se rade prikradejo v naše zapiske. Zato raje poskusimo
napisati podprogram , ki bo to "zoprno" in zamudno delo opravil namesto nas.
Tako dopolnjeni Evklidov algoritem bomo imenovali razširjeni Evklidov algo-
ritem. Seveda pa moramo postopek sprogramirati tako, da bomo prepričani,
da deluje pravilno, in da bomo znali to svoje prepričanje tudi ustrezno uteme-
ljiti. Zato si najprej na prejšnjem primeru oglejmo nekoliko drugačen in bolj
pregleden zapis razširjenega Evklidovega algoritma:
120
1 . 882 + O. 270
O. 882 + 1 . 270
1 . 882 + (-3) · 270
(-3) . 882 + 10·270
4 ·882 + (-13) ·270
(-15) ·882 + 49·270
= 882
= 270 / · 3
72 / ·3
54/ ·1
18 / . 3
O
Prvi dve vrstici zgornje sheme trdita očitno resnico o obeh vhodnih podat-
kih. Nato z desnimi stranmi enakosti opravimo običajni Evklidov algoritem:
izračunamo celoštevilski kvocient med zadnjima dvema desnima stranema ,
pomnožimo z njim zadnjo enačbo in jo odštejemo od predzadnje. Ko je desna
stran nove enačb e enaka O, se ustavimo . Predzadnja enačba je iskani zapis
največjega skupnega delitelja kot celoštevilske kombinacije začetn ih števil a
in b. Mimogrede nam zadnja enačba razkrije še najmanjši skupni večkratnik
začetnih števil a in b. V prejšnjem primeru je to 15·882 =49 ·270 =13230.
Da je to vedno res, naj se bralec prepriča sam.
Zgornje sheme pa ni težko zapisati v obliki podprograma v pascalu .
function razsGCD(a.b: int eger; var xO.yO: integer) : integer ;
{ Poi~če največji skupni delitelj števil a in b ter njegov zap is kot}
{celo~tevilsko kombinacijo števi! a in b s koeficientoma x O in y O. }
var
xl,yl ,k,t : integer;
begin
xO:=I ; yO:=O;
xl :=O; yl :=l ;
while b<>O do begin
k:=a div b;
t:=b; b:=a-k*b ; a:=t;
t:=xl ; xl :=xO-k*xl ; xO:=t;
t :=yl; yl :=yO-k*yl ; yO:=t;
end ;
razsGCD:=a;
end ; {razsGCD}
Poskusimo še nekoliko analizirati Evklidov algoritem. Koliko deljenj
moramo opraviti v najslabšem primeru, če z Evklidovim algoritmom iščemo
največji skupni delitelj naravnih števil a in b? Odgovor na to vprašanje je
povezan s Fibonaccijevimi števili. To je zaporedje števil fI, f2, f3, . . . , ki je
določeno takole. Prva dva člena zaporedja sta enaka 1: torej fI = f2 =
= 1, vsak nadaljnji člen pa je vsota predhodnih dveh: fnH = fn + fn-l za
121
n ~ 2. Začetek zaporedja Fibonaccijevih števil je tako 1,1,2,3,5,8,13, ....
Z indukcijo se zlahka prepričamo, da potrebujemo za izračun največjega
skupnega delitelja števil fn+l in fn z Evklidovim algoritmom natanko n deljenj.
Ko namreč oprav imo prvo deljenje, je ostanek ravno število fn- l . Za izračun
največjega skupnega delitelja števil fn in fn- l po indukcijski predpostavki
potrebujemo n-1 deljenj, skupaj torej natanko n. (Mimogrede tudi opazimo,
da sta zaporedni Fibonaccijevi števili tuji.)
Pokažirno še nekakšen obrat zgornje trditve . Naj bosta a in b naravni
števili, pri kater ih je Evklidov algoritem potreboval natanko n deljenj za
izračun njunega največjega skupnega delitelja . Privzeli bomo, da je a > b.
Ostanke, ki se pojavijo v algoritmu, označimo z rl, r2, . . . , rn = O, kvociente
pa s kI, k2, ... , k n. Posebej definiramo r-l = a in ro = b. Pri izračunu
gcd(882, 270) je torej zaporedje ostankov 882,270,72,54 ,18, O, zaporedje
kvocientov pa je 3,3 ,1 ,3. Ker so kvocienti in ostanki dobljeni z Evklidovim
algoritmom, za 1 :s i :s n velja ri-2 = ki ri-l + ri. Z matematično
indukcijo bomo pokazali , da velja ri ~ fn-i za i = n - 1, n - 2, . . . ,0,-1.
Ker je zaporedje ostankov strogo padajoče, vsi č l e n i razen zadnjega pa so
pozitivni, ocena velja pri i = n - 1 in pri i = n - 2. Opravimo še indukcijski
korak. Prejšnji ostanek ri-2 je enak kiri-l + ri , to število pa po indukcijski
predpostavki ni manjše od fn-(i-l) + fn-i = fn-(i-2) ' Pri oceni smo tudi
upoštevali, da so vsi kvocienti ki naravna števila , torej večji ali enaki 1. Ocene
za velikost ostankov so s tem dokazane.
Le v izpeljane neenakosti vstavimo i = -1 in i = O, vidimo, da je
a ~ fn+l in b ~ fn. Zaporedni Fibonaccijevi števili fn+l in fn torej
tvorita najmanjši par različnih naravnih števil, pri katerih Evklidov algoritem
potrebuje za izračun največjega skupnega delitelja n deljenj .
Označimo s r.p razmerje zlatega reza, torej r.p = ~. Pokažimo, da
je fn ~ r.pn-2. Oceno dokažerno z matematično indukcijo. Za n = 1 in
n = 2 trditev očitno drži . Izpeljimo še indukcijski korak. Privzemi mo, da je
fn ~ r.pn-2 in fn- l ~ r.pn-3 . Potem pa je tud i fn+l = fn + fn- l ~ r.pn-2 +
+ r.pn-3 = r.pn-3( r.p + 1) = r.pn-3 r.p2 = r.pn-l, saj je~ + 1 =(~)2 .
Gornji rezultat o številu deljenj, ki jih potrebuje Evklidov algoritem, lahko
povemo tudi nekoliko drugače. Ker je a ~ fn+l ~ r.pn-l, z logaritmiranjem
dobimo log", a ~ n - 1. Stevilo deljenj n, ki jih opravi Evklidov algoritem, je
torej kvečjemu 1 + log", a.
Martin Juvan