Inhalt

Grundlagen der Mathematik

Diskrete Mathematik

Kombinatorik

Graphentheorie

Zahlentheorie

Geschichtliches

Natürliche Zahlen

Ganze Zahlen

Konstruktion aus den

natürlichen Zahlen

Gaußklammer

Erweiterter

euklidischer Algorithmus

Elementare Zahlentheorie

Analytische Zahlentheorie

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist eine Erweiterung des euklidischen Algorithmus. Die Eingabe besteht aus zwei Zahlen a und b und der Algorithmus liefert den größten gemeinsamen Teiler d sowie zwei ganze Zahlen s und t mit und liefert damit einen konstruktiven Beweis für

Satz 164U (Lemma von Bézout)

Der größte gemeinsame Teiler g zweier ganzer Zahlen a und b lässt sich als Linearkombination von a und b mit ganzzahligen Koeffizienten darstellen:

mit . Insbesondere sind a und b genau dann teilerfremd, wenn es gibt, so dass

gilt.

Allgemeiner gilt das Lemma von Bézout in jedem Hauptidealring (siehe Satz 164T).

Beschreibung des Algorithmus

Der Algorithmus sieht wie folgt aus:

Setze m = a, n = b, s = 1, t = 0, u = 0, v = 1
Berechne q und r mit m = (Division mit Rest)
Setze m = n, n = r, ,
Setze s = u, t = v, u = u', v = v'
Falls n ? 0 gehe zu Schritt (ii).

Nach Beendigung ist .

Man kann dieses Vorgehen in der folgenden Form übersichtlich darstellen:

a	=	+
b	=	+
	=	+
m	=	+
n	=	+
r = m - qn	=	+

Dabei ist q der ganzzahlige Anteil von m/n

Man zieht also immer von der vorletzten Zeile die mit q multiplizierte letzte Zeile ab, um die nächste Zeile zu erhalten. Wenn die Abbruchbedingung n = 0 erfüllt ist, gilt m = r = ggT(a, b) und folglich

Die Größen u und v werden für die praktische Berechnung nicht benötigt und können zur Verbesserung der Effizienz weggelassen werden.

Beispiel

Für a = 37 und b = 16 ergibt sich:

37	=	+
16	=	+	(q = 2)
5	=	-	(q = 3)
1	=	+	(q = 5)
0	=	-

Also ist .

Beziehung zu Kettenbrüchen

Die Folge der auftretenden Zahlen q liefert die Kettenbruchdarstellung von a/b. Für obiges Beispiel erhalten wir:

Das entscheidende Kriterium ist Schönheit; für häßliche Mathematik ist auf dieser Welt kein beständiger Platz.

Godfrey Harold Hardy

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: