Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist eine Erweiterung des euklidischen Algorithmus. Für zwei Zahlen aa und bb ermittelt er ihren größten gemeinsamen Teiler dd sowie zwei ganze Zahlen ss und tt mit d=s⋅a+t⋅bd = s\cdot a + t\cdot b und liefert damit einen konstruktiven Beweis für

Satz 164U (Lemma von Bézout)

Der größte gemeinsame Teiler dd zweier ganzer Zahlen aa und bb lässt sich als Linearkombination von aa und bb mit ganzzahligen Koeffizienten darstellen:
d=s⋅a+t⋅bd = s \cdot a + t \cdot b
mit s,t∈Zs,t\in\mathbb{Z}. Insbesondere sind aa und bb genau dann teilerfremd, wenn es s,t∈Zs,t\in\mathbb{Z} gibt, so dass
1=s⋅a+t⋅b1 = s \cdot a + t \cdot b
gilt.
 
 

Beschreibung des Algorithmus

Der Algorithmus sieht wie folgt aus:
  1. Setze mm = aa, nn = bb, ss = 1, tt = 0, uu = 0, vv = 1
  2. Berechne qq und rr mit mm = q⋅n+rq\cdot n + r (Division mit Rest)
  3. Setze m=nm = n, n=rn =r, u′=s−q⋅uu' = s - q \cdot u, v′=t−q⋅vv' = t - q \cdot v
  4. Setze ss = uu, tt = vv, u=u′u = u', v=v′v = v'
  5. Falls n>0n >0 gehe zu Schritt (ii).
Nach Beendigung ist ggT⁡(a,b)=m=s⋅a+t⋅b\ggT(a,b)= m = s\cdot a + t\cdot b.

Beispiel

Für a=37a=37 und b=16b=16 ergibt sich:
3737 == 1⋅371\cdot 37 ++ 0⋅160\cdot 16
1616 == 0⋅370\cdot 37 ++ 1⋅161\cdot 16 (q=2)(q=2)
55 == 1⋅371\cdot 37 −- 2⋅162\cdot 16 (q=3)(q=3)
11 == (−3)⋅37(-3)\cdot 37 ++ 7⋅167\cdot 16 (q=5)(q=5)
00 == 16⋅3716\cdot 37 −- 37⋅1637\cdot 16.
Also ist ggT⁡(37,16)=1=(−3)⋅37+7⋅16\ggT(37,16)=1=(-3)\cdot37+7\cdot 16.

Beziehung zu Kettenbrüchen

Die Folge der auftretenden Zahlen qq liefert die Kettenbruchdarstellung von a/ba/b. Für obiges Beispiel erhalten wir:
3716=2+13+15 \dfrac{37}{16} = 2+\dfrac1{3+\dfrac15}\,

Hochtechnologie ist im wesentlichen mathematische Technologie.

Enquete-Kommission der Amerikanischen Akademie der Wissenschaften

Copyright- und Lizenzinformationen: Diese Seite ist urheberrechtlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Zahlentheorie