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.
Eukleideen algoritmi etenee seuraavasti:
Esimerkkejä.
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.
Esimerkki 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:
formula_1
formula_2
formula_3
formula_4
formula_5
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:
formula_6
formula_7
formula_8
formula_9
formula_10
formula_11
formula_12
formula_13.
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 formula_14, 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":
Todistus.
Että Eukleideen algoritmi antaa tuloksena lukujen suurimman yhteisen tekijän, voidaan osoittaa kaksivaiheisella todistuksella. Ensin osoitetaan, että viimeinen nollasta poikkeava jakojäännös "r""N"−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 formula_15 Toisessa vaiheessa osoitetaan, että "r""N"−1 on jaollinen jokaisella "a":n ja "b":n yhteisellä tekijällä, siis myös niiden suurimmalla yhteisellä tekijällä "g", mistä seuraa, että formula_16. Näistä kahdesta epäyhtälöstä seuraa, että formula_17
Ensimmäisessä vaiheessa siis osoitetaan, että sekä "a" että "b" ovat jaollisia luvulla "r""N"−1. Edellinen jakojäännös "r""N"−2 on jaollinen "r""N"−1:llä, 
 formula_18
koska viimeinen jakojäännös "r""N" on nolla. Myös sitä edeltävä jakojäännös "r""N"−3 on jaollinen "r""N"−1:llä
 formula_19
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 "r""N"−1. Mikään aikaisemmista jakojäännöksistä, "r""N"−2, "r""N"−3 jne. ei ole "a":n ja "b":n tekijä, koska jäljelle jäi jakojäännös. Koska "r""N"−1 on "a":n ja "b":n yhteinen tekijä, on "r""N"−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 "r""k":n tekijä (eli "r""k" 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, "r"0, on jaollinen "c":llä, koska "r"0 = "a" − "q"0"b" = "mc" − "q"0"nc" = ("m" − "q"0"n")"c". Vastaavalla tavalla osoittautuu, että "c" on myös jaollinen kaikilla myöhemmillä jakojäännöksillä "r"1, "r"2, jne.
Siksi suurimman yhteisen tekijän "g" on oltava myös "r""N"−1:n tekijä, mistä seuraa, että "g" ≤ "r""N"−1. Koska todistuksen ensimmäisessä vaiheessa osoitettiin, että kääntäen ("r""N"−1 ≤ "g"), seuraa tästä, että "g" = "r""N"−1. Näin ollen "g" on lukujen "a" ja "b" sekä samalla kaikkien ketjussa peräkkäisten lukujen suurin yhteinen tekijä:
 formula_20.
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.
Eukleideen algoritmi on yksi vanhimmista yhä käytössä olevista algoritmeista. Se esitellään Eukleideen "Alkeet" -teoksen 10. kirjassa lauseena 2 sekä eri pituisia janoja koskevana geometrisena lauseena myös 10. kirjassa lauseena 3. 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. Matemaatikko ja historioitsija B. L. van der Waerden arvelee, että Eukleideen 7. kirja on alkujaan ollut Pythagoraan koulukunnassa käytetty lukuteoriaa käsittelevä oppikirja. Todennäköisesti algoritmin tunsi ainakin jo Eudoksos Knidolainen noin vuonna 375 eKr, mutta mahdollisesti se oli tunnettu jo ennen häntäkin, mihin viittaa se seikka, että Eukleides ja Aristoteles käyttivät teknistä termiä ἀνθυφαίρεσις ("anthyphairesis", "käänteinen vähennyslasku".
Satoja vuosia myöhemmin Eukleideen algoritmi keksittiin kreikkalaisista riippumatta sekä Intiassa että Kiinassa, 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"), luultavasti sen vuoksi, koska se tarjosi niin tehokkaan keinon yhtälöiden ratkaisemiseksi. Vaikka jo Sun Zu kolmannella vuosisadalla esitti erään erikoistapauksen kiinalaisesta jäännöslauseesta, yleisen ratkaisun esitti Qin Jiushao vuonna 1247 teoksessaan "Shushu Jiuzhang" (數書九章 "Yhdeksänosainen matemaattinen tutkielma")
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. Euroopassakin sitä käytettiin Diofantoksen yhälöiden ratkaisemiseen sekä myös ketjumurtolukujen kehittämiseen. Yleistetyn Eukleideen algoritmin julkaisi englantilainen matemaatikko Nicholas Saunderson joka väitti Roger Cotesin jo aikaisemmin kehittäneen sen menetelmäksi ketjumurtolukujen tehokkaaseen käsittelyyn.
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. Gauss mainitsi algoritmin jo vuonna 1801 julkaisemassaan teoksessa "Disquisitiones Arithmeticae", mutta vain ketjumurtolukujen käsittelyyn liittyvänä keinona. Peter Dirichlet näyttää olleen ensimmäinen, joka osoitti Eukleideen algoritmin merkityksen perustana suurelle osalle lukuteoriaa. Hän osoitti, että monet lukuteorian tulokset, kuten yksikäsitteinen alkutekijöihin jako, pätevät jokaisessa lukualueessa, johon Eukleideen algoritmia voidaan soveltaa. 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, formula_21, jos ja vain jos formula_22. 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.
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.
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) ja Lenstran–Lenstran–Lovászin algoritmi (LLL-algoritmi)
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", which has an optimal strategy. 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.
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.