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:

• 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:

$408=112\cdot \,3 72$

$112=72\cdot \,1 40$

$72=40\cdot \,1 32$

$40=32\cdot \,1 8$

$32=8\cdot \,4 0$

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:

$a=q_{0}b r_{0},\ 0<r_{0}<|b|$

$b=q_{1}r_{0} r_{1},\ 0<r_{1}<|r_{0}|$

$r_{0}=q_{2}r_{1} r_{2},\ 0<r_{2}<|r_{1}|$

$r_{1}=q_{3}r_{2} r_{3},\ 0<r_{3}<|r_{2}|$

$r_{2}=q_{4}r_{3} r_{4},\ 0<r_{4}<|r_{3}|$

$r_{3}=q_{5}r_{4} r_{5},\ 0<r_{5}<|r_{4}|$

...

$r_{n-2}=q_{n}r_{n-1} r_{n},\ 0<r_{n}<|r_{n-1}|$

$r_{n-1}=q_{n 1}r_{n} 0\$.

Algoritmi päättyy, koska luvut r₀, r₁, ...,r_n muodostavat aidosti vähenevän jonon positiivisia kokonaislukuja.

Viimeinen jakojäännös r_n jakaa (tasan) luvut a ja b:

Alimmasta yhtälöstä r_n jakaa luvun r_n-1.
Koska $r_{n-2}=q_{n}r_{n-1} r_{n}$, niin r_n jakaa luvun r_n-2
Näin jatkamalla saadaan lopulta, että r_n 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 r₀, r₁, ... yllä olevien yhtälöiden nojalla. Näin siis c jakaa luvun r_n, 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. 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 $r_{N-1}\leq g$ 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ä $r_{N-1}\geq g$. Näistä kahdesta epäyhtälöstä seuraa, että $r_{N-1}=g$

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ä,

$r_{N-2}=q_{n}r_{N-1}$

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ä

$r_{N-3}=q_{N-1}r_{N-2} r_{N-1}$

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_NrN−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 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₀, on jaollinen c:llä, koska r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c. Vastaavalla tavalla osoittautuu, että c on myös jaollinen kaikilla myöhemmillä jakojäännöksillä r₁, r₂, 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ä:

$g={\text{syt}}(a,b)={\text{syt}}(b,r_{0})={\text{syt}}(r_{0},r_{1})={\text{syt}}(R_{N-2},R_{N-1})=r_{N-1}$.

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 menetelmä kahden janan, BA ja DC, pituuksien suurimman yhteisen tekijän määrittämiseksi, kun molempien pituudet ovat saman "yksikköjanan" pituuden monikertoja. Kun DC on lyhempi, sitä käytetään BA:n "mittaamiseen", mutta vain kerran, koska jäljelle jäävä osa EA on lyhyempi kuin DC. EA mittaa nyt kahteen kertaan pienemmän alkuperäisistä janoista DC, jolloin jäljelle jäävä osa FC on pienempi kuin EA. Tämän jälkeen EA mittaa (kolmeen kertaan) pituuden EA. Koska jako nyt menee tasan, voidaan lopettaa tähän ja todeta, että suurin yhteinen tekijä on FC. Oikealla Nikomakhoksen esimerkki luvuilla 49 ja 21, joiden suurimmaksi yhteiseksi tekijäksi osoittautuu 7.

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, $p=x^{2} y^{2}$, jos ja vain jos $p\equiv 1{\pmod {4}}$. 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.

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

• Eukleideen algoritmi, online sovellus