Euclidalgoritmen

Euclidalgoritmen, eller Euclids algoritm, är en metod för att beräkna största gemensamma delaren (ggd) av två heltal. Den används också för att hitta heltalskoefficienterna i Bézouts identitet. Grundidén är att om två tal a och b finns, så kan man skriva a = bq + r. Då gäller gcd(a,b) = gcd(b,r). Genom att upprepa processen med talen b och r fås successivt mindre tal tills resten blir 0. Den sista icke-noll-resten är gcd(a,b).

Exempel: gcd(48,18) ger 48 = 18×2 + 12; 18 = 12×1 + 6; 12 = 6×2 + 0, så gcd(48,18) = 6. Algoritmen kan implementeras både iterativt och rekursivt och används ofta med två variabler som uppdateras i varje steg.

Komplexiteten är effektiv i praktiken och växlar med divisionernas kostnad; i grova termer är antalet steg ungefär logaritmiskt i minsta av talen. Denna egenskap gör algoritmen snabb även för mycket stora heltal.

Historiskt är namnet knutet till den antika grekiske matematikern Euclid. Algoritmen beskrevs i Elements och har varit ett grundläggande verktyg inom aritmetik och talteori sedan dess.

Variant och utbyggnader: För att även finna x och y sådana att ax + by = gcd(a,b) används den förlängda Euclids algoritm. Det finns även den binära (Steins) algoritm som använder subtraktioner och bitförskjutningar istället för division, ofta använd i datorimplementationer. Användningsområden inkluderar modulär aritmetik, beräkning av modulära inverser, samt olika kryptografiska och numeriska algoritmer.