Euklides algoritm

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.[2] Algoritmen kräver inte att man kan dela upp talen i faktorer.

Algoritmen kan beskrivas på följande sätt:[1]

  1. Två heltal a och b, där a > b är givna.
  2. Om b = 0 är algoritmen klar och svaret är a.
  3. I annat fall beräknas c, resten när man delat a med b.
  4. 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.

steg a b c kommentar 1 , 2 1071 1029 − 3 1071 1029 42 1071 = 1 ⋅ 1029 + 42 4 , 2 1029 42 − b ≠ 0 3 1029 42 21 1029 = 24 ⋅ 42 + 21 4 , 2 42 21 − b ≠ 0 3 42 21 0 42 = 2 ⋅ 21 4 , 2 21 0 − b = 0 {\displaystyle {\begin{array}{l|ccc|l}{\textrm {steg}}&a&b&c&{\textrm {kommentar}}\\\hline 1,2&1071&1029&-&\\3&1071&1029&42&1071=1\cdot 1029+42\\4,2&1029&42&-&b\neq 0\\3&1029&42&21&1029=24\cdot 42+21\\4,2&42&21&-&b\neq 0\\3&42&21&0&42=2\cdot 21\\4,2&21&0&-&b=0\\\end{array}}}

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 Bézouts identitet, som säger 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:

21 = 1029 − 24 ⋅ 42 {\displaystyle 21=1029-24\cdot 42}
42 = 1071 − 1 ⋅ 1029 {\displaystyle 42=1071-1\cdot 1029}
⇒ 21 = 1029 − 24 ⋅ 42 = 1029 − 24 ⋅ ( 1071 − 1 ⋅ 1029 ) = 1029 ⋅ 25 − 1071 ⋅ 24 {\displaystyle \Rightarrow 21=1029-24\cdot 42=1029-24\cdot (1071-1\cdot 1029)=1029\cdot 25-1071\cdot 24}

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 x = 1.5 {\displaystyle \!x=1.5} så är frac ( x ) = 0.5 {\displaystyle {\mbox{frac}}\left(x\right)=0.5} och om x ∈ Z {\displaystyle x\in \mathbb {Z} } , så är decimaldelen noll, det vill säga frac ( x ) = 0 {\displaystyle {\mbox{frac}}\left(x\right)=0} .

a = 1071 {\displaystyle a=1071}
b = 1029 {\displaystyle b=1029}
c = 1029 ⋅ frac ( 1071 1029 ) = 42 {\displaystyle c=1029\cdot {\mbox{frac}}\left({\frac {1071}{1029}}\right)=42}
a = b = 1029 {\displaystyle a=b=1029}
b = c = 42 {\displaystyle b=c=42}
c = 42 ⋅ frac ( 1029 42 ) = 21 {\displaystyle c=42\cdot {\mbox{frac}}\left({\frac {1029}{42}}\right)=21}
a = b = 42 {\displaystyle a=b=42}
b = c = 21 {\displaystyle b=c=21}
c = 21 ⋅ frac ( 42 21 ) = 0 {\displaystyle c=21\cdot {\mbox{frac}}\left({\frac {42}{21}}\right)=0}
a = b = 21 {\displaystyle a=b=21}
b = c = 0 {\displaystyle b=c=0}

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 a b {\displaystyle {\frac {a}{b}}} blir a = b q + r {\displaystyle a=bq+r}

  c | b {\displaystyle \ c|b}
  c | r {\displaystyle \ c|r}
  c | b q {\displaystyle \ c|bq}
  c | b q + r {\displaystyle \ c|bq+r}

Då måste alltså alla tal som delar r och b dela a

  c | a {\displaystyle \ c|a}

Så sgd(a, b)=sgd(b, r)

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.

Referenser

  1. ^ [a b] ”Euklides algoritm”. Nationalencyklopedin. http://www.ne.se/uppslagsverk/encyklopedi/lång/euklides-algoritm. Läst 3 september 2016. 
  2. ^ För rationella tal i bok VII, för reella tal i bok X. Se Weisstein, Eric W., "Euclidean Algorithm", MathWorld. (engelska)

Externa länkar

  • Wikimedia Commons har media som rör Euklides algoritm.
    Bilder & media