Eukleideen algoritmi
Eukleideen algoritmi on Eukleideen mukaan nimetty menetelmä, jonka avulla voidaan selvittää kahden kokonaisluvun suurin yhteinen tekijä (syt). Algoritmi perustuu jakoyhtälön perättäiseen käyttöön.[1]
Eukleideen algoritmi etenee seuraavasti:
- Ensin kirjoitetaan jakoyhtälö luvuilla a ja b
- Seuraavaksi kirjoitetaan jakoyhtälö luvulle b ja edellisen jakoyhtälön jakojäännökselle
- Aiempi jakojäännös jaetaan uudella jakojäännöksellä
- Toistetaan niin usein, että jakojäännökseksi saadaan nolla.
- Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös
Esimerkkejä
Alla kaksi esimerkkiä.
1.
Määritetään lukujen 48 ja 18 suurin yhteinen tekijä eli syt(48,18). Toisin sanoen a = 48 ja b = 18
a : b = 2 kokonaista ja jakojäännös on 12 (48:18 on 2 kokonaista ja 12 on jakojäännös)
b : 12 = 1 kokonainen ja jakojäännös on 6
12 : 6 = 2 ja jakojäännös on 0.
Suurin yhteinen tekijä luvuilla 48 ja 18 on siis 6 eli viimeinen luku, jolla esimerkissä jaettiin.
2.
Määritetään lukujen 112 ja 408 suurin yhteinen tekijä eli syt(112, 408).
Määritetään lukujen suurin yhteinen tekijä Eukleideen algoritmin avulla:
Lukujen 112 ja 408 suurin yhteinen tekijä on siis kahdeksan eli syt(112, 408)=8.
Suoritus peräkkäisten jakokulmien avulla
Edellä johdetut laskutoimitukset voidaan kynällä ja paperilla laskettaessa suorittaa myös peräkkäisten jakokulmien avulla seuraavalla tavalla:
48|18 -36| 2 18| 12 -12| 1 12| 6 -12| 2 0
408|112 -336| 3 112| 72 -72| 1 72| 40 -40| 1 40| 32 -32| 1 32| 8 -32| 4 0
Tässä käytetyt ja toisiinsa yhdistetyt jakokulmat ovat ns. italialaisia jakokulmia, joissa jaettava, jakaja ja osamäärä sijoitetaan seuraavasti:
jaettava | jakaja | osamäärä.
Ensimmäisessä jakolaskussa on suurempi alkuperäisistä luvuista jaettavana, pienempi jakajana. Kussakin jakokulmassa on ylävasemmalla jaettava ja yläoikealla jakaja. Osamäärän kokonaisosa merkitään alaoikealle, kun taas alavasemmalla suoritetaan vähennyslasku, josta saadaan jakojäännös. Kun jakolasku on suoritettu, jaetaan edellisen jakolaskun jakaja saadulla jakojäännöksellä, mikä suoritetaan merkitsemällä se jakojäännöksen vasemmalle puolelle ja suorittamalla jakolasku tavalliseen tapaan. Näin jatketaan, kunnes jakojäännös on nolla, jolloin viimeinen sitä edeltänyt jakaja (tässä esimerkissä 8) on alkuperäisten lukujen suurin yhteinen tekijä.
Yleinen tapaus
Olkoot luvut a ja b kokonaislukuja ja b erisuuri kuin nolla. Käyttämällä toistuvasti jakoyhtälöä saadaan:
...
- .
Algoritmi päättyy, koska luvut r0, r1, ...,rn muodostavat aidosti vähenevän jonon positiivisia kokonaislukuja.
Viimeinen jakojäännös rn jakaa (tasan) luvut a ja b:
Alimmasta yhtälöstä rn jakaa luvun rn-1.
Koska , niin rn jakaa luvun rn-2
Näin jatkamalla saadaan lopulta, että rn jakaa b:n ja a:n.
Jos luvuilla a ja b on yhteinen tekijä c, ts. sanoen a ja b ovat tasan jaollisia luvulla c, c jakaa luvun r0, r1, ... yllä olevien yhtälöiden nojalla. Näin siis c jakaa luvun rn, joka on siten yhteisistä tekijöistä suurin.
Kiinalaisten käyttämä algoritmi
Kiinalaiset suorittivat saman algoritmin helmitaulussa seuraavasti:
Vähennä toistuvasti pienempi luku suuremmasta. Kun luvut ovat keskenään yhtä suuret, algoritmi päättyy ja kyseinen luku on suurin yhteinen tekijä.
Esimerkki etsitään syt(15,25).
25 = 1 * 15 + 10.
15 = 1 * 10 + 5.
10 = 2 * 5 + 0.
eli syt(15,25) = 5.
"Kiinalaisittain":
25 | 10 | 10 | 5 |
15 | 15 | 5 | 5 |
Todistus
Että Eukleideen algoritmi antaa tuloksena lukujen suurimman yhteisen tekijän, voidaan osoittaa kaksivaiheisella todistuksella.[2] Ensin osoitetaan, että viimeinen nollasta poikkeava jakojäännös rN−1 on sekä a:n että b:n tekijä eli sekä a että b ovat sillä jaollisia. Koska se on niiden yhteinen tekijä, on se on joko pienempi tai yhtä suuri kuin niiden suurin yhteinen tekijä g, toisin sanoen Toisessa vaiheessa osoitetaan, että rN−1 on jaollinen jokaisella a:n ja b:n yhteisellä tekijällä, siis myös niiden suurimmalla yhteisellä tekijällä g, mistä seuraa, että . Näistä kahdesta epäyhtälöstä seuraa, että
Ensimmäisessä vaiheessa siis osoitetaan, että sekä a että b ovat jaollisia luvulla rN−1. Edellinen jakojäännös rN−2 on jaollinen rN−1:llä,
koska viimeinen jakojäännös rN on nolla. Myös sitä edeltävä jakojäännös rN−3 on jaollinen rN−1:llä
koska molemmat yhtälön oikealla puolella olevat termit ovat sillä jaollisia. Samaa päättelyä toistamalla todetaan, että kaikki edeltävät jakojäännökset sekä lopulta myös alkuperäiset luvut a ja b oat jaollisia luvulla rN−1. Mikään aikaisemmista jakojäännöksistä, rN−2, rN−3 jne. ei ole a:n ja b:n tekijä, koska jäljelle jäi jakojäännös. Koska rNrN−1 on a:n ja b:n yhteinen tekijä, on rN−1 ≤ g.
Toisessa vaiheessa osoitetaan, että jokainen luonnollinen luku c, jolla sekä a että b ovat jaollisia (toisin sanoen jokainen a:n ja b:n yhteinen tekijä) on myös rk:n tekijä (eli rk on jaollinen c:llä). Määritelmän mukaan a ja b voidaan esittää c:n monikertoina: a = mc and b = nc, missä m and n ovat luonnollisia lukuja. Näin ollen ensimmäinen jakojäännös, r0, on jaollinen c:llä, koska r0 = a − q0b = mc − q0nc = (m − q0n)c. Vastaavalla tavalla osoittautuu, että c on myös jaollinen kaikilla myöhemmillä jakojäännöksillä r1, r2, jne. Siksi suurimman yhteisen tekijän g on oltava myös rN−1:n tekijä, mistä seuraa, että g ≤ rN−1. Koska todistuksen ensimmäisessä vaiheessa osoitettiin, että kääntäen (rN−1 ≤ g), seuraa tästä, että g = rN−1. Näin ollen g on lukujen a ja b sekä samalla kaikkien ketjussa peräkkäisten lukujen suurin yhteinen tekijä:[3]
- .
Sovelluksia
Eukleideen algoritmilla on monia teoreettisia ja käytännöllisiä sovelluksia. Ensinnäkin sen avulla voidaan sieventää murtolukuja, sillä osoittajan ja nimittäjän suurin yhteinen tekijä on suurin luku, jolla murtoluku voidaan supistaa. Sen avulla voidaan myös suorittaa jakolaskuja modulaariaritmetiikassa. Tähän algoritmiin perustuvat laskutoimitukset muodostavat myös osan salausprotollista, joiden avulla varmistetaan Internet-yhteyksien turvallisuus, mutta myös keinoissa, joilla tämä salaus puretaan jakamalla suuret luvut alkutekijöihin. Eukleideen algoritmilla voidaan myös ratkaista Diofantoksen yhtälöitä, esimerkiksi sellaisten lukujen etsimiseksi, jotka kiinalaisen jäännöslauseen mukaisesti toteuttavat moninkertaisia kongruensseja. Sitä käytetään myös ketjumurtolukujen konstruointiin sekä rationaalisten likiarvojen määrittämiseksi reaaliluvuilla. Sen avulla voidaan myös todistaa monia lukuteorian keskeisiä tuloksia, esimerkiksi Lagrangen neljän neliön lause sekä aritmetiikan peruslause, jonka mukaan jokainen yhtä suurempi kokonaisluku voidaan yhdellä ja vain yhdellä esittää alkulukujen tulona.
Historia
![Käännös suomeksi](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Translation_Latin_Alphabet.svg/60px-Translation_Latin_Alphabet.svg.png)
Alkuperäinen artikkeli: en:Euclidean algorithm
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/96/Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg/300px-Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg.png)
Eukleideen algoritmi on yksi vanhimmista yhä käytössä olevista algoritmeista.[4] Se esitellään Eukleideen Alkeet -teoksen 10. kirjassa lauseena 2[5] sekä eri pituisia janoja koskevana geometrisena lauseena myös 10. kirjassa lauseena 3.[6] Jälkimmäinen todistus osoittaa, miten kahden janan ollessa yhteismitalliset löydetään jana, jonka pituus sisältyy tasan kummankin janan pituuteen.
Todennäköisesti Eukleides ei itse keksinyt algoritmia, vaan se tunnettiin jo ennen hänen aikaansa.[7][8] Matemaatikko ja historioitsija B. L. van der Waerden arvelee, että Eukleideen 7. kirja on alkujaan ollut Pythagoraan koulukunnassa käytetty lukuteoriaa käsittelevä oppikirja.[9] Todennäköisesti algoritmin tunsi ainakin jo Eudoksos Knidolainen noin vuonna 375 eKr, mutta mahdollisesti se oli tunnettu jo ennen häntäkin,[10] mihin viittaa se seikka, että Eukleides ja Aristoteles käyttivät teknistä termiä ἀνθυφαίρεσις (anthyphairesis, "käänteinen vähennyslasku".[11]
Satoja vuosia myöhemmin Eukleideen algoritmi keksittiin kreikkalaisista riippumatta sekä Intiassa että Kiinassa,[12] joissa sitä käytettiin lähinnä tähtitieteessä ja tarkkojen kalenterien laskennassa tarvittavien Diofantoksen yhtälöiden ratkaisemisessa. Intialainen matemaatikko ja tähtitieteilijä Aryabhata 400-luvun lopulla nimitti erästä algoritmin yleistystä "pulverisoijaksi" (Kuttaka)[13], luultavasti sen vuoksi, koska se tarjosi niin tehokkaan keinon yhtälöiden ratkaisemiseksi.[14] Vaikka jo Sun Zu kolmannella vuosisadalla esitti erään erikoistapauksen kiinalaisesta jäännöslauseesta[15], yleisen ratkaisun esitti Qin Jiushao vuonna 1247 teoksessaan Shushu Jiuzhang (數書九章 Yhdeksänosainen matemaattinen tutkielma)[16]
Euroopassa Eukleideen algoritmin esitteli ensimmäisenä numeerisesti ja teki yleisesti tunnetuksi Bachet'n teoksen Problèmes plaisants et délectables (Hauskoja ja huvittavia probleemoja) toinen painos vuodelta 1624.[17] Euroopassakin sitä käytettiin Diofantoksen yhälöiden ratkaisemiseen sekä myös ketjumurtolukujen kehittämiseen. Yleistetyn Eukleideen algoritmin julkaisi englantilainen matemaatikko Nicholas Saunderson[18] joka väitti Roger Cotesin jo aikaisemmin kehittäneen sen menetelmäksi ketjumurtolukujen tehokkaaseen käsittelyyn.[19]
1800-luvulla Eukleideen algoritmi johti uusien lukualueiden kuten Gaussin kokonaislukujen ja Eisensteinin kokonaislukujen keksimi]]seen. Vuonna 1815 Carl Friedrich Gauss osoitti Eukleideen algoritmin avulla, että Gaussin kokonaisluvut voidaan yksikäsitteisellä tavalla jakaa alkutekijöihin, joskin todistus julkaistiin vasta vuonna 1832.[20] Gauss mainitsi algoritmin jo vuonna 1801 julkaisemassaan teoksessa Disquisitiones Arithmeticae, mutta vain ketjumurtolukujen käsittelyyn liittyvänä keinona.[12] Peter Dirichlet näyttää olleen ensimmäinen, joka osoitti Eukleideen algoritmin merkityksen perustana suurelle osalle lukuteoriaa.[12] Hän osoitti, että monet lukuteorian tulokset, kuten yksikäsitteinen alkutekijöihin jako, pätevät jokaisessa lukualueessa, johon Eukleideen algoritmia voidaan soveltaa.[21] Hänen lukuteoriaa käsittelevää tutkielmaansa muokkasi ja laajensi Richard Dedekind, joka tutki Eukleideen algoritmin avulla uutta yleistä lukualuetta, algebrallisia kokonaislukuja. Dedekind muun muassa todisti ensimmäisenä Fermat'n kahden neliön lauseen, jonka pariton alkuluku p voidaan esittää kahden kokonaisluvun neliöiden summana, , jos ja vain jos . Dedekind määritteli myös euklidisen alueen käsitteen. Sillä tarkoitetaan lukualuetta, jossa yleistetty versio Eukleideen algoritmista voidaan määritellä. 1800-luvun lopuolla Eukleideen algoritmi kuitenkin jäi vähitellen Dedekindin yleisemmän ideaalien teorian varjoon.[12]
1800-luvulla Eukleideen algoritmille keksittiin muitakin sovelluksia. Vuonna 1829 Charles Sturm osoitti sen käyttökelpoisuuden määritettäessä Sturmin ketjun avulla annetun polynomin niiden tietyllä välillä olevia nollakohtia.[22]
Eukleideen algoritmi on vanhin tunnettu keino, jonka avulla yhteismitallisille reaaliluvuille voidaan löytää kokonaislukusuhteita. Nykyaikana on keksitty muitakin kokonaislukujen suhteisiin perustuvia algoritmeja kuten Helaman Fergusonin ja R.W. Forcaden algoritmi (1979)[23] ja Lenstran–Lenstran–Lovászin algoritmi (LLL-algoritmi)[24][25]
Vuonna 1969 Cole ja Davie kehittivät Eukleideen algoritmiin perustuvan kahden henkilön pelin nimeltä ääThe Game of Euclid In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid,[26] which has an optimal strategy.[27] Pelin alussa kummallakin pelaajalla on kasa kiviä, toisella a ja toisella b kappaletta. Sitten pelaajat vuorotellen poistavat suuremmasta kasasta m kertaa pienemmässä kasassa olevien kivien lukumäärän. Jos siis pinoissa jollakin hetkellä on x ja y kiveä ja x on suurempi kuin y, vuorossa oleva pelaaja poistaa suuremmasta kasasta my kiveä, jolloinisen kasan tyhjennetyksi kokonaan.[28]
Donald Knuth on nimittänyt Eukleideen algoritmia "kaikkien algoritmien isoisäksi", koska se on vanhin ei-triviaali algoritmi, joka on pysynyt käytössä nykyaikaan saakka.[4]
Lähteet
- ↑ Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 92. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.
- ↑ H. Stark: An Introduction to Number Theory, s. 16–20. MIT Press, 1978. ISBN 0-262-69060-8.
- ↑ László Lovász: Discrete Mathematics: Elementary and Beyond, s. 100–101. New York: Springer-Verlag, 2003. ISBN 0-387-95584-4.
- ↑ a b D. E. Knuth: The Art of Computer Programming, Vol 2: Seminumerical Algorithms (3rd ed.), s. 318. Addison-Wesley, 1997. ISBN 0-387-94777-9.
- ↑ Eukleides: ”Book VII (Fundamentals of Number Theory), Proposition 2 Julkaisija = aleph0.clarku.edu”, Euclid's Elements. {{{Julkaisija}}}. Teoksen verkkoversio.
- ↑ Eukleides: ”Book 10 (Classification of Incommensurables), Proporision 3”, Euclid's Elements. aleph0.clarku.edu. Teoksen verkkoversio.
- ↑ André Weil: Number Theory, s. 4–6. Birkhäuser, 1983. ISBN 0-8176-3141-0.
- ↑ A. Jones: ”Greek mathematics to AD 300”, Companion encyclopedia of the history and philosophy of the mathematical sciences, s. 46–48. New York: Routledge, 1994. ISBN 0-415-09238-8.
- ↑ Bartel Leendert van der Waerden: Science Awakening, s. 114–. englanniksi kääntänyt Arnold Dresden. Groningen: P. Noordhoff Ltd. Teoksen verkkoversio.
- ↑ Euclid’s Algorithm (GCD) ((Footnote 1)) uvm.edu.
- ↑ O. Becker: Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid. Quellen und Studien zur Geschichte der Mathematik B, 1933, nro 2, s. 311–333.
- ↑ a b c d John Stillwell: Numbers and Geometry, s. 31–32. Springer-Verlag, 1997. ISBN 0-387-98289-2.
- ↑ The Aryabhata Algorithm Using Least Absolute Remainders arxiv.org. Viitattu 7.6.2024.
- ↑ K. H. Rosen: Elementary Number Theory and its Applications (4th ed.). Reading, Massachusetts: Addison-Wesley, 2000. ISBN 0-201-87073-8.
- ↑ O. Ore: Number Theory and Its History, s. 247–248. New York: McGraw-Hill, 1948.
- ↑ J. J. Tattersall: Elementary Number Theory in Nine Chapters, s. 72, 184–185. Cambridge: Cambridge University Press, 2005 ISBN 978-0-521-85014-8.
- ↑ J. J. Tattersall: Elementary Number Theory in Nine Chapters, s. 70. Cambdidge: Cambridge University Press, 2005. ISBN 978-0-521-85014-8. Teoksen verkkoversio.
- ↑ Nicholas Saunderson: The Elements of Algebra in Ten Books. University of Cambridge Press, 1740. Teoksen verkkoversio.
- ↑ J. J. Tattersall: Elementary Number Theory in Nine Chapters, s. 72–76. Cambdidge: Cambridge University Press, 2005 ISBN 978-0-521-85014-8.
- ↑ C. F. Gauss: Theoria residuorum biquadraticorum. Comm. Soc. Reg. Sci. Gött. Rec, 1832, nro 4. Artikkelin verkkoversio.
- ↑ Richard Dedekind (toim.); P. G. Lejeune Dirichlet: Vorlesungen über Zahlentheorie, s. 29–31. Braunschweig: Vieweg, 1894. (saksaksi)
- ↑ Charles Sturm: Mémoire sur la résolution des équations numériques. Bull. Des sciences de Férussac, 1829, nro 11, s. 419–422. (ranskaksi)
- ↑ Helaman Ferguson, R. W. Forcade: Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two. Bulletin of the American Mathematical Society, New Series, 1979, 1. vsk, nro 6, s. 912–914. doi:10.1090/S0273-0979-1979-14691-3.
- ↑ I. Peterson: Jazzing Up Euclid's Algorithm. ScienceNews, 12.8.2002. Artikkelin verkkoversio.
- ↑ Barry Arthur Cipra: The Best of the 20th Century: Editors Name Top 10 Algorithms. SIAM News, 16.5.2000, 33. vsk, nro 4. Society for Industrial and Applied Mathematics. Artikkelin verkkoversio.
- ↑ A. J. Cole; A. J. T. Davie: A game based on the Euclidean algorithm and a winning strategy for it. Math. Gaz., 1969, 53. vsk, nro 386, s. = 354–357. doi:10.2307/3612461.
- ↑ E. L. Spitznagel: Properties of a game based on Euclid's algorithm. Math. Mag., 1973, 46. vsk, nro 2, s. 87–92. doi:10.2307/2689037.
- ↑ J. Roberts: Elementary Number Theory: A Problem Oriented Approach, s. 1–8. Cambridge, Massachusetts: MIT Press, 1977. ISBN = 0-262-68028-9. Teoksen verkkoversio.
Kirjallisuutta
- Kaleva, Osmo: Numeerinen analyysi. Opintomoniste 163. Tampere: TTKK, 1993. ISBN 951-721-941-5.
- Häsä, Jokke & Rämö, Johanna: Johdatus abstraktiin algebraan. Helsinki: Gaudeamus, 2015. ISBN 978-952-495-361-0.
Aiheesta muualla
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- Eukleideen algoritmi, online sovellus