Povzetek V prispevku je na kratko opisana zgodovina Evklidovega algorit- ma. Navedene so nekatere njegove klasične uporabe v teoriji šte- vil: Bezoutova identiteta, reševanje linearnih diofantskih enačb, uporaba pri kitajskem izreku o ostankih, aproksimacija korenov naravnih števil z verižnimi ulomki in reševanje Pellove enačbe. Prispevek se konča s posplošitvijo na evklidske kolobarje, kjer so omenjeni kolobarji polinomov v eni spremenljivki s koeficienti iz obsega, Gaussova števila in Eisensteinova števila. Ključne besede: zgodovina matematike, Evklidov algoritem, Bezoutova identiteta, linearne diofantske enačbe, kitajski izrek o ostankih, verižni ulomki, Pellova enačba, evklidski kolobar Evklidov algoritem Marjan Jerman Univerza v Ljubljani, Fakulteta za matematiko in fiziko Euclidean Algorithm Abstract The article briefly describes the history of Euclidean algorithm. Descri- bed within are some classical methods of its use in the theory of numbers: Bézout's identity, solving linear Diophantine equations, its application on the Chinese remainder theorem, approximation of the roots of natu- ral numbers with help of continued fractions, and solving Pell's equation. The article concludes with a generalization based on Euclidean doma- ins, mentioning the domains of polynomials in one variable with coef- ficients from a division ring, Gaussian integers and Eisenstein integers. Keywords: history of mathematics, Euclidean algorithm, Bézout's iden- tity, linear Diophantine equations, Chinese remainder theorem, conti- nued fractions, Pell's equation, Euclidean domain Matematika v šoli XIX. [2013] 054-060 55 α Uvod Evklidov algoritem je prvič omenjen v Ev- klidovih Elementih 1 , vendar so ga poznali že dosti prej. Pitagorejci 2 so verjetno z njegovo pomočjo računali zelo natančne približke korenov naravnih števil. V sedmi knjigi Ele- mentov je zelo strnjeno zapisana različica algoritma za cela števila, ki nam izračuna največji skupni delitelj dveh naravnih števil: Zaporedoma odštevaj manjše število od večjega, dokler manjše število ne postane deli- telj večjega. Takrat je manjše od števil največji skupni delitelj začetnih števil. V deseti knjigi Elementov je opisana ge- ometrijska različica Evklidovega algoritma, s pomočjo katere lahko Evklidov algoritem do neke mere posplošimo na realna števila. Za dani daljici pravimo, da sta soizmerljivi, če obstaja takšna (krajša) daljica, imenovana skupna mera daljic, da je vsaka od danih da- ljic enaka celemu številu kopij krajše daljice. Tudi v geometrijskem primeru poteka Evkli- dov algoritem skoraj enako kot prej: Zaporedoma odštevaj krajšo daljico od več- je. Če po nekaj korakih dobiš enaki daljici, si s tem dobil največjo skupno mero začetnih dal- jic. Če se postopek v končnem številu korakov ne konča z enakima daljicama, začetni daljici nista soizmerljivi. V modernem matematičnem jeziku bi lahko rekli, da sta realni števili soizmerljivi, če je njun kvocient racionalno število. V srednji šoli običajno povemo Evklidov algoritem za naravni števili kot eno od mož- 1 Evklidovi Elementi so zbirka 13 knjig iz tretjega stole- tja pr. Kr., ki povzemajo najpomembnejše starogrško znanje matematike. 2 Pitagora (570-500 pr. Kr.). Na jugu Italije, ki je bil tedaj del antične Grčije, je ustanovil versko-filozofsko bratovščino, ki se je ukvarjala s teoretično matemati- ko, glasbo in astronomijo. nosti za iskanje največjega skupnega delitel- ja teh dveh števil. V nadaljevanju prispevka bodo opisane še nekatere druge pomembne uporabe algoritma, ki so zaradi elementarno- sti velikokrat dostopne tudi srednješolcem, ki želijo poglobiti svoje znanje matematike. β Bezoutova identiteta Naj bosta m in n naravni števili z največ- jim skupnim deliteljem D in n ≥ m. Evklidov algoritem poteka takole: Preberimo Evklidov algoritem v obrat- nem vrstnem redu: Iz predzadnje enačbe lahko izrazimo D kot . Na enak način preberemo , zato velja tudi . V vsakem naslednjem koraku s pomoč- jo višje ležečih vrstic v Evklidovem algorit- mu vsak ostanek zamenjamo s celoštevilsko k o m b i naci jo ost a n k o v r t-1 in r t-2 . Skupni deli- telj D tako vsakič napišemo kot celoštevilsko kombinacijo ostankov z nižjima indeksoma. Prva vrstica nam pove Bezoutovo identi- teto 3 3 Étienne Bézout (1730-1783), francoski matematik Evklidov algoritem 56 D = mx + ny za primerni celi števili x in y. Poglejmo si jo za par naravnih števil 67 in 120. Najprej izvedimo Evklidov algoritem: 120 = 1 ∙ 67 + 53 67 = 1 ∙ 53 + 14 53 = 3 ∙ 14 + 11 14 = 1 ∙ 11 + 3 11 = 3 ∙ 3 + 2 3 = 2 ∙ 1 + 1 Največji skupni delitelj 1 lahko sedaj na- pišemo kot celoštevilsko kombinacijo števil 67 in 120: 1 = 3 - 2 = 3 – (11 – 3 ∙ 3) = 4 ∙ 3 - 11 = = 4 ∙ (14 – 11) – 11 = 4 ∙ 14 – 5 ∙ 11 = = 4 ∙ 14 – 5 ∙ (53 – 3 ∙ 14) = 19 ∙ 14 – 5 ∙ 53 = = 19 ∙ (67 – 53) – 5 ∙ 53 = 19 ∙ 67 – 24 ∙ 53 = = 19 ∙ 67 – 24 ∙ (120 – 67) = 43 ∙ 67 – 24 ∙ 120 Razcep ni enoličen. Na primer, velja tudi: 1 = (43 + 120) ∙ 67 – (24 + 67) ∙ 120 δ Linearne diofantske enabe Naj bosta m in n naravni števili z največ- jim skupnim deliteljem D. Če je rešljiva line- arna diofantska enačba mx + ny = c, je jasno, da mora D deliti tudi c, c = Dc' . Bezoutova identiteta nam pove, da velja tudi obratno. Če D deli c, lahko najdemo celi števili x' in y', za kateri velja D = mx' + ny' in tako dobimo eno od rešitev diofantske enačbe: c = Dc' = m(x' c') + n(y' c'). Če je m = Dm' in n = Dn', lahko D v dio- fantski enačbi pokrajšamo. S tem dosežemo, da sta števili m' in n' tuji. Lahko je videti 4 , da so vse rešitve enačbe m'x + n'y = 1 oblike x = x' + kn', y = y' – km' . Rešitve enačbe m'x + n'y = c' pa so le ustrezno pomnožene, x = c'x' + kn', y = c'y' – km'. Rešimo na primer diofantsko enačbo 67x + 120y = 3. V prejšnjem razdelku smo dobili razcep 1 = 43 ∙ 67 – 24 ∙ 120 Zato so vse rešitve enačbe 67x+120y=1 oblike x = 43 + 120k, y = -24 – 67k rešitve enačbe 67x + 120y = 3 pa oblike x = 3 ∙ 43 + 120k, y = -3 ∙ 24 – 67k, x = 9 + 120l, y = -5 – 67l V teoriji kodiranja je zelo pomembno iskanje multiplikativnih inverzov iz obsega ostankov po praštevilskem modulu Z p , kjer je p praštevilo. Če je m Z p \{0}, dobimo m -1 Z p \{0} kot rešitev diofantske enačbe mx = 1 + py Ker je p praštevilo, sta si števili m in p tuji in enačba je rešljiva s samo eno rešitvijo x {1,2, ... p – 1}. Tako recimo inverz elementa 14 v obsegu Z 23 dobimo z reševanjem diofantske enačbe 14x – 23k = 1 4 To je verjetno prvi uvidel indijski matematik Brahma- gupta (598-670). 57 Iz Evklidovega algoritma za 14 in 23 23 = 14 + 9 12 = 9 + 5 9 = 5 + 4 5 = 4 + 1 dobimo: 1 = 5 – 4 = 5 – (9 – 5) = 2 ∙ 5 – 9 = 2 ∙ (14 – 9) – 9 = = 2 ∙ 14 – 3 ∙ 9 = 2 ∙ 14 – 3 ∙ (23 – 14) = 5 ∙ 14 – 3 ∙ 23 Zato je 5 multiplikativni inverz elementa 14 v obsegu Z 23 . Res je 5 ∙ 14 = 70 =1. ε Kitajski izrek o ostankih V slavni klasični kitajski matematični knjigi Devet poglavij matematičnih spretnosti iz drugega stoletja, v kateri je zbrano kitajsko znanje matematike od 10. stoletja pr. Kr. na- prej, je zapisana naslednja naloga: Skupina prijateljev prispeva za skupen na- kup. Če vsak plača po 8 kovancev, zberejo tri kovance preveč. Če pa vsak da po 7 kovan- cev, zmanjkajo štirje. Poišči število prijateljev in znesek nakupa. Z vidika stroge moderne matematike manjka še dodatna zahteva, da iščemo naj- manjše možno število prijateljev v skupini. Rešitev sicer ni enolična. Iščemo torej najmanjše naravno število, ki da pri delitvi z 8 ostanek 3, pri delitvi s 7 pa ostanek -4. V knjigi je še več podobnih nalog, vse pa lahko posplošimo na reševanje sistema kon- gruenc: x a 1 (mod m 1 ) x a 2 (mod m 2 ) x a k (mod m k ) Kitajski izrek o ostankih pove, da je ta sis- tem zagotovo rešljiv, če so moduli paroma tuji. Prvi algoritem za reševanje sistema je zapisal indijski matematik Aryabhata 5 . Zvito je ugotovil, da je treba rešitev x iskati v obliki x = x 1 m 2 m 3 m k + x 2 m 1 m 3 m 4 + m k + + x k m 1 m 2 m k-1 . Vsak od seštevancev je deljiv z vsemi mo- duli, razen z enim, zato lahko problem pre- vedemo na reševanje več lažjih in manjših problemov oblike x t m 1 m t-1 m t+1 m k a t (mod m t ), 1 ≤ t ≤ k, vsak od njih pa je ekvivalenten reševanju ustrezne linearne diofantske enačbe, ki jo lahko rešimo s pomočjo Evklidovega algo- ritma. Pri naši kitajski nalogi torej rešujemo sis- tem kongruenc x -3 (mod 8), x 4 (mod 7). Modula 8 in 7 sta si tuja, zato je sistem reš- ljiv. Rešitev iščemo z nastavkom x = 8x 1 + 7x 2 pri čemer morata x 1 in x 2 ustrezati dio- fantskima enačbama 8 x 1 = 7k + 4 7 x 2 = 8l – 3. Na enak način kot prej lahko najdemo re- šitve teh diofantskih enačb: x 1 = 4 + 7m, k = 4 + 8m, x 2 = 3 + 8n, l = 3 + 7n, zato je x = 8(4 + 7m) + 7(3 + 8n) = 53 + 56(m + n). 5 Aryabhata (476-550), indijski matematik Najmanjše naravno število, ki ustreza zgor nji zahtevi, je x = 53. Če 7 prijateljev pri- speva po 8 kovancev, je zbranih 56 kovancev za 3 preveč, če pa prispevajo po 7 kovancev, je zbranih 49 za 4 premalo. γ Verižni ulomki Evklidov algoritem za realna števila je na prvi pogled zelo nenavaden, je pa že Pitago- rejcem služil za iskanje izjemno dobrih pri- bližkov korenov naravnih števil. Poglejmo si, kako lahko najdemo zapored- ne približke za √2. Evklidov algoritem za √2 in 1 se sicer za- radi iracionalnosti števila √2 nikoli ne konča, a med računanjem opazimo zelo jasen vzorec: √2 = 1 ∙ 1 + (√2 – 1) 1 = 2 ∙ (√2 – 1) + (3 – 2√2) √2 – 1 = 2 ∙ (3 – 2√2) + (5√2 – 7) 3 – 2√2 = 2 ∙ (5√2 – 7) + (17 – 12√2) Sorazmernostne dvojke se v vseh nasled- njih korakih ponavljajo. Posamezne korake algoritma bi lahko zapisali tudi drugače: Običajno na kratko napišemo, da številu √2 ustreza periodičen neskončni verižni ulomek √2 = [1; 2, 2, 2, …] = [1; 2]. Ker se ostanki z vsakim korakom Evklido- vega algoritma manjšajo, dobivamo čedalje boljše približke za √2: Izkaže se, da se da vsak koren naravnega števila, ki ni popoln kvadrat, zapisati s peri- odičnim verižnim ulomkom, ki pa je lahko veliko bolj zapleten, recimo √61=[7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14]. Približki za korene z verižnimi ulomki so v vseh primerih zelo dobri. Zaporedna raci- onalna aproksimacija se od prave vrednosti korena razlikuje za manj kot . Na primer: Z neskončnimi verižnimi ulomki se da na- pisati celo transcendentna števila, na primer π = [3; 7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,...], ki pa seveda nimajo periode. Presenetljivo lahko najdemo vzorec v verižnem ulomku za osnovo naravnega logaritma e: e = [2; 1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1,… ]. Naj bo n naravno število, ki ni popoln kvadrat. Diofantski enačbi x 2 – ny 2 = 1 pravimo Pellova enačba. 6 Enačbo lahko rešimo tako, da najprej z Evklidovim algoritmom poiščemo verižni ulomek za √n. Prvi od okrajšanih približ- kov , ki jih dobimo z računanjem veriž nega ulomka in ustreza Pellovi enačbi, je osnov- na rešitev (x 1 , y 1 ) enačbe. Vse druge rešitve (x k , y k ) so z osnovno povezane z enačbo 6 Enačbo je Euler pomotoma poimenoval po angleškem matematiku Johnu Pellu (1611-1685). Natančno je njene rešitve opisal William Brouncker (1620-1684), poznali pa so jih že indijski matematiki v 12. stoletju. V posebnih primerih so jo znali rešiti že Pitagorejci. Evklidov algoritem 58 59 x k + y k √n = (x 1 + y 1 √n) k . Na primer, pri reševanju enačbe x 2 – 7y 2 = 1 si pomagamo z verižnim ulomkom Med zaporednimi približki , , , , ... naj- demo osnovno rešitev x 1 = 8, y 1 = 3. Ostale rešitve dobimo iz enakosti x k + y k √7 = (8 + 3√7) k . η Posplošitve Evklidovega algoritma Evklidov algoritem za naravni števili se vedno konča v končno korakih zato, ker se ostanki v vsakem naslednjem koraku algo- ritma strogo manjšajo. S to idejo lahko Ev- klidov algoritem izvajamo tudi v veliko bolj splošnih algebrskih strukturah. Naj bo N množica naravnih števil in K komutativen kolobar. Kolobar K je evklidski kolobar, če obstaja funkcija φ: K\{0} → N {0} z naslednjima lastnostma: 1. Če za a, b K velja ab ≠ 0, je φ (a) ≤ φ (ab). 2. Za a, b K, b ≠ 0, obstajata elementa q, r K, tako da je a = qb + r. Pri tem je bodisi r = 0 bodisi r ≠ 0 in φ(r) < φ(b). Druga lastnost nam zagotavlja, da lahko v kolobarju K izvajamo Evklidov algoritem, ki se konča po končno korakih. Poglejmo si nekaj najpomembnejših pri- merov evklidskih kolobarjev. Običajni Evklidov algoritem dobimo v primeru K = Z in φ(x) = |x|. Zelo pomemben primer so polinomi v eni spremenljivki s koeficienti iz komutativnega obsega, na primer R[x]. Za φ(p) vzamemo stopnjo polinoma p. Za ilustracijo z Evklidovim algoritmom poiščimo največji skupni delitelj polinomov x 4 + x 3 + 2x 2 – 1 in x 2 + x – 1: Njun največji skupni delitelj je konstanta, zato sta si polinoma tuja. Na enak način kot v celih številih lahko s pomočjo Evklidovega algoritma rešujemo tudi polinomske linearne diofantske enačbe in si z njim pomagamo pri uporabi kitajske- ga izreka o ostankih. Algoritem nam poma- ga tudi pri tvorbi Sturmovega zaporedja 7 , ki nam prešteje realne ničle polinoma na da- nem intervalu. Podmnožici kompleksnih števil Z[i] = {a + bi; a, b Z\}, opremljeni z običajnima operacijama, pravimo Gaussova števila 8 . Za funkcijo φ vzamemo običajno razdaljo kom- pleksnega števila od izhodišča: φ (a + bi) = a 2 + b 2 . Zanimivo je, da se da s pomočjo obrav- nave kolobarja Z[i] dobiti nekaj pomembnih lastnosti običajnih celih števil, ki bi jih bilo težko dokazati neposredno. Z Gaussovimi števili se da recimo zelo elegantno poiskati Pitagorejske trojice. Prav tako se da pokazati, da je možno praštevila, ki dajejo pri deljenju s 4 ostanek 1, napisati kot vsoto dveh celošte- vilskih kvadratov. 7 Jacques Charles François Sturm (1803-1855), franco- ski matematik 8 Carl Friedrich Gauss (1777-1855), nemški matema- tik, astronom in fizik Evklidov algoritem 60 V teoriji števil so pomembna tudi podob- no skonstruirana Eisensteinova števila 9 oblike z ustrezno funkcijo φ (a + bω) = a 2 – ab + b 2 . Vsako naravno število se da na le en način napisati kot produkt potenc praštevil (pravi- mo, da je K kolobar kolobar z enolično fak- torizacijo). Prav tako drži zanimivo dejstvo, da za naravni števili in z največjim skupnim deliteljem D velja {am + bn; a, b Z} = {cD; c Z} (rečemo, da je kolobar Z glavni). V bolj splo- šnih algebrskih strukturah veljajo le inkluzije: vsak evklidski kolobar je glavni, vsak glavni kolobar pa je kolobar z enolično faktorizacijo. ϕ asovna zahtevnost Evklidovega algoritma Zaradi široke uporabnosti Evklidovega algoritma v računalništvu je zelo pomembna tudi njegova časovna zahtevnost. Algoritem 9 Ferdinand Gotthold Max Eisenstein (18231852), nemški matematik za naravni števili n > m se konča prej kot v 5d korakih, kjer je d število števk števila m. 10 Zanimivo je, da algoritem poteka najpočas- neje v primeru dveh zaporednih elementov Fibonaccijevega 11 zaporedja. Povprečno šte- vilo korakov Evklidovih algoritmov za vse pare (m, n), m < n, je približno 0,843 ∙ ln n. λ Zakljuek Evklidov algoritem je lep primer, kako po- gosto za na videz standardno, rutinsko in ne preveč impresivno temo iz srednješolskega kurikuluma stoji navdušujoča zgodovina iz- jemnih idej, ki so jih skoraj istočasno zaradi praktičnih potreb neodvisno odkrivale različne civilizacije. Osnovne ideje ljudstev, ki abstrak- cije niti niso znali zapisati v simboličnem zapi- su, so postale temelji moderne matematike. Zato upam, da bo pričujoči prispevek slu- žil tudi kot ena od idej, kako matematiko na zanimiv način približati srednješolcem. 10 Gabriel Leon Jean Baptiste Lamé (1795-1870), fran- coski matematik 11 Leonardo Pisano Bigollo-Fibonacci (1170-1250), italijanski matematik. Fibonaccijevo zapored- je lahko definiramo z dvočleno rekurzivno zvezo F n+2 = F n+1 + F n in začetnima členoma F 1 = F 2 = 1. δ Viri in literatura: 1. W . S. Anglin, Mathematics: a concise history and philo- sophy, Undergraduate Texts in Mathematics, Readings in Mathematics, Springer-Verlag, New Y ork, 1994. 2. T. W . Hungerford, Algebra, Graduate Texts in Mathe- matics, Springer-Verlag, New Y ork, 1974. 3. J. J. T attersall, Elementary number theory in nine chap- ters, Cambridge University Press, 1999. 4. I. Vidav, Algebra, 4. natis, DMFA, Ljubljana, 1989. 5. The Mac Tutor History of Mathematics archive, http:// www-history.mcs.st-and.ac.uk/, citirano 11. 10. 2012.