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?
Formel mit Erklärung
- 1Runter: den normalen euklidischen Algorithmus durchführen (a = q · b + r), bis der Rest 0 ist.
- 2Die vorletzte Zeile nach dem ggT (dem letzten Rest ungleich 0) umstellen.
- 3Rauf: Zeile für Zeile den kleinsten Rest durch seine Darstellung aus der Zeile darüber ersetzen (Rest = a − q · b).
- 4Nach jedem Einsetzen zusammenfassen, sodass nur noch die zwei Zahlen der Zeile darüber vorkommen.
- 5Oben angekommen steht da: ggT = s · a + t · b. Probe rechnen!
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
