Euklides algoritm
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2016-08) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
Euklides algoritm är en algoritm för att bestämma största gemensamma delare till två heltal[1]. Det är en av de äldsta kända algoritmerna och beskrivs i Euklides Elementa. Algoritmen kräver inte att man kan dela upp talen i faktorer.
Algoritmen kan beskrivas på följande sätt:[1]
- Två heltal a och b, där a > b är givna.
- Om b = 0 är algoritmen klar och svaret är a.
- I annat fall beräknas c, resten när man delat a med b.
- sätt a = b, b = c och börja om från steg 2 igen, (a får det värde b har och b får det värde c har).
Exempel 1
Finn den största gemensamma delaren till 1071 och 1029.
Den största gemensamma delaren är alltså 21.
Kortare skrivet:
- 1071 = 1 · 1029 + 42
- 1029 = 24 · 42 + 21
- 42 = 2 · 21 + 0, så svaret är 21.
En snabb kontroll bekräftar att 1071 = 51 · 21 och 1029 = 49 · 21.
En följd av Euklides algoritm är att den största gemensamma delaren till två tal a,b kan skrivas som en linjärkombination av talen ax+by (x,y heltal). Genom att lösa ut resterna och köra algoritmen baklänges bestämmer man x och y. I exemplet ovan:
Detta kan användas vid lösning av den diofantiska ekvationen ax + by = c.
Exempel 2
Nedan följer en alternativ metod som fungerar lika bra som ovan. Med funktionen frac menas decimaldelen av talet. Om så är och om , så är decimaldelen noll, det vill säga .
Bevis för Euklides algoritm
Euklides använde sig av ett så kallat motsägelsebevis. Han utgick från att det finns ett tal c som delar b och r, men inte a. Och att divisionen blir
Då måste alltså alla tal som delar r och b dela a
Så sgd(a, b)=sgd(b, r)
Exempel i Python
def sgd(a, b):
if b == 0:
return a
return sgd(b, a % b)
Generalisering av Euklides algoritm
Euklides algoritm kan utvidgas till att operera på andra ringar än heltalen, som ovan. Ringar i vilka Euklides algoritm kan användas kallas Euklidiska ringar. Exempel på Euklidiska ringar är de Gaussiska heltalen och vissa polynomringar.
Källor
- ^ [a b] ”Euklides algoritm”. Nationalencyklopedin. http://www.ne.se/uppslagsverk/encyklopedi/lång/euklides-algoritm. Läst 3 september 2016.
Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia. |