Eukleideen algoritmi
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,  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.