Erweiterter euklidischer Algorithmus

Mit dem Euklidischer Algorithmus|euklidischen Algorithmus finden wir den ggT. Manchmal wollen wir aber mehr wissen: Wie setzt sich der ggT aus den beiden Zahlen zusammen? Beispiel: Du hast nur 14 -Liter- und 10 -Liter-Eimer. Kannst du damit genau 2 Liter abmessen? Ja: 3 -mal 10 Liter einfüllen und 2 -mal 14 Liter wieder herausschöpfen: 3 cdot 10 - 2 cdot 14 = 30 - 28 = 2 Solche Zahlen ( 3 und -2 ) findet der erweiterte euklidische Algorithmus . Gebraucht wird er vor allem, um in der Zahlentheorie Inverse zu berechnen – zum Beispiel bei der RSA-Verschlüsselung. Lemma von Bézout Zu zwei natürlichen Zahlen a und b gibt es immer ganze Zahlen s und t mit text{ggT}(a, b) = s cdot a + t cdot b Eine der beiden Zahlen s , t ist dabei meist negativ. Plan: erst runter, dann wieder rauf Tipp: Die Zahlen, die eingesetzt werden, nicht ausrechnen – nur zusammenfassen. Sonst verliert man die Spur. Finde s und t mit text{ggT}(14, 10) = s cdot 14 + t cdot 10 . Runter: 14 = 1 cdot 10 + 4 10 = 2 cdot 4 + mathbf{2} 4 = 2 cdot 2 + 0 qquad Rightarrow qquad text{ggT} = 2 Rauf: Zweite Zeile nach 2 umstellen, dann 4 = 14 - 1 cdot 10 einsetzen: 2 = 10 - 2 cdot 4 = 10 - 2 cdot (14 - 1 cdot 10) = 10 - 2 cdot 14 + 2 cdot 10 = 3 cdot 10 - 2 cdot 14 Ergebnis: s = -2 , t = 3 . Probe: -2 cdot 14 + 3 cdot 10 = -28 + 30 = 2 ✓ Finde s und t mit text{ggT}(96, 76) = s cdot 96 + t cdot 76 . Runter: 96 = 1 cdot 76 + 20 76 = 3 cdot 20 + 16 20 = 1 cdot 16 + mathbf{4} 16 = 4 cdot 4 + 0 qquad Rightarrow qquad text{ggT}

Worum geht's?

Mit dem euklidischen Algorithmus finden wir den ggT. Manchmal wollen wir aber mehr wissen: Wie setzt sich der ggT aus den beiden Zahlen zusammen? Beispiel: Du hast nur 14 14 14 -Liter- und 10 10 10 -Liter-Eimer. Kannst du damit genau 2 2 2 Liter abmessen? Ja: 3 3 3 -mal 10 10 10 Liter einfüllen und 2 2 2 -mal 14 14 14 Liter wieder herausschöpfen: 3 ⋅ 10 − 2 ⋅ 14 = 30 − 28 = 2 3 \cdot 10 - 2 \cdot 14 = 30 - 28 = 2 3 ⋅ 10 − 2 ⋅ 14 = 30 − 28 = 2 Solche Zahlen ( 3 3 3 und − 2 -2 − 2 ) findet der erweiterte euklidische Algorithmus . Gebraucht wird er vor allem, um in der Zahlentheorie Inverse zu berechnen – zum Beispiel bei der RSA-Verschlüsselung.

Formel mit Erklärung

Lemma von Bézout Zu zwei natürlichen Zahlen a a a und b b b gibt es immer ganze Zahlen s s s und t t t mit ggT ( a , b ) = s ⋅ a + t ⋅ b \text{ggT}(a, b) = s \cdot a + t \cdot b ggT ( a , b ) = s ⋅ a + t ⋅ b Eine der beiden Zahlen s s s , t t t ist dabei meist negativ. Plan: erst runter, dann wieder rauf
Erweiterter euklidischer Algorithmus
  1. 1
    Runter: den normalen euklidischen Algorithmus durchführen (a = q · b + r), bis der Rest 0 ist.
  2. 2
    Die vorletzte Zeile nach dem ggT (dem letzten Rest ungleich 0) umstellen.
  3. 3
    Rauf: Zeile für Zeile den kleinsten Rest durch seine Darstellung aus der Zeile darüber ersetzen (Rest = a − q · b).
  4. 4
    Nach jedem Einsetzen zusammenfassen, sodass nur noch die zwei Zahlen der Zeile darüber vorkommen.
  5. 5
    Oben angekommen steht da: ggT = s · a + t · b. Probe rechnen!
Tipp: Die Zahlen, die eingesetzt werden, nicht ausrechnen – nur zusammenfassen. Sonst verliert man die Spur.

Beispiele

Leicht#1
Finde s s s und t t t mit ggT ( 14 , 10 ) = s ⋅ 14 + t ⋅ 10 \text{ggT}(14, 10) = s \cdot 14 + t \cdot 10 ggT ( 14 , 10 ) = s ⋅ 14 + t ⋅ 10 . Runter: 14 = 1 ⋅ 10 + 4 14 = 1 \cdot 10 + 4 14 = 1 ⋅ 10 + 4 10 = 2 ⋅ 4 + 2 10 = 2 \cdot 4 + \mathbf{2} 10 = 2 ⋅ 4 + 2 4 = 2 ⋅ 2 + 0 ⇒ ggT = 2 4 = 2 \cdot 2 + 0 \qquad\Rightarrow\qquad \text{ggT} = 2 4 = 2 ⋅ 2 + 0 ⇒ ggT = 2 Rauf: Zweite Zeile nach 2 2 2 umstellen, dann 4 = 14 − 1 ⋅ 10 4 = 14 - 1 \cdot 10 4 = 14 − 1 ⋅ 10 einsetzen: 2 = 10 − 2 ⋅ 4 = 10 − 2 ⋅ ( 14 − 1 ⋅ 10 ) = 10 − 2 ⋅ 14 + 2 ⋅ 10 = 3 ⋅ 10 − 2 ⋅ 14 2 = 10 - 2 \cdot 4 = 10 - 2 \cdot (14 - 1 \cdot 10) = 10 - 2 \cdot 14 + 2 \cdot 10 = 3 \cdot 10 - 2 \cdot 14 2 = 10 − 2 ⋅ 4 = 10 − 2 ⋅ ( 14 − 1 ⋅ 10 ) = 10 − 2 ⋅ 14 + 2 ⋅ 10 = 3 ⋅ 10 − 2 ⋅ 14 Ergebnis: s = − 2 s = -2 s = − 2 , t = 3 t = 3 t = 3 . Probe: − 2 ⋅ 14 + 3 ⋅ 10 = − 28 + 30 = 2 -2 \cdot 14 + 3 \cdot 10 = -28 + 30 = 2 − 2 ⋅ 14 + 3 ⋅ 10 = − 28 + 30 = 2 ✓

Zusammenfassung

Der erweiterte euklidische Algorithmus liefert ggT und Zahlen s , t s, t s , t mit ggT ( a , b ) = s ⋅ a + t ⋅ b \text{ggT}(a, b) = s \cdot a + t \cdot b ggT ( a , b ) = s ⋅ a + t ⋅ b . Ablauf: erst runter (normaler Euklid), dann rauf (Reste Zeile für Zeile einsetzen und zusammenfassen). Eingesetzte Zahlen nicht ausrechnen, nur zusammenfassen – und am Ende die Probe machen. Ist ggT ( a , m ) = 1 \text{ggT}(a, m) = 1 ggT ( a , m ) = 1 , liefert er das Inverse von a a a modulo m m m (negatives Ergebnis: m m m addieren).

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: