Was ist Abi-Mathe?
Themen
Tools
Abi-Mathe supporten geht ganz leicht. Einfach über diesen Link bei Amazon
shoppen (ohne Einfluss auf die Bestellung). Gerne auch als Lesezeichen speichern.
Euklidischer Algorithmus
- Euklidischer Alorithmus, Bestimmung des ggT (7:45 Minuten)
- Online Rechner: Euklidischer Algorithmus (ggT)
Einleitung
Der euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen.
Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt, der es in seinem Werk „Die Elemente“ beschrieben hat.
Der größte gemeinsame Teiler zweier Zahlen kann auch aus ihren Primfaktorzerlegungen ermittelt werden. Ist aber von keiner der beiden Zahlen die Primfaktorzerlegung bekannt, so ist der euklidische Algorithmus das schnellste Verfahren zur Berechnung des größten gemeinsamen Teilers.
Verfahren
Für die Berechnung des ggT von zwei Zahlen \( a \) und \( b \) teilt man zunächst die größere Zahl durch die kleinere. Ist der Rest Null, dann ist der ggT die kleinere Zahl von beiden. Andernfalls ist der ggT gleich dem ggT von der kleineren Zahl und dem Rest.
Beispiel
Berechnung des größten gemeinsamen Teilers von \( 234 \) und \( 324 \).
| \( 324 \) | \( = \) | \( 1 \) | \( \cdot \) | \( 234 \) | \( + \) | \( 90 \) | ||
| \( 234 \) | \( = \) | \( 2 \) | \( \cdot \) | \( 90 \) | \( + \) | \( 54 \) | ||
| \( 90 \) | \( = \) | \( 1 \) | \( \cdot \) | \( 54 \) | \( + \) | \( 36 \) | ||
| \( 54 \) | \( = \) | \( 1 \) | \( \cdot \) | \( 36 \) | \( + \) | \( 18 \) | ||
| \( 36 \) | \( = \) | \( 2 \) | \( \cdot \) | \( 18 \) | \( + \) | \( 0 \) |
Der ggT ist der letzte von Null verschiedene Rest.
$$ \text{ggT}(234, \, 324) = 18 $$
Quellen
- Wikipedia: Artikel über "Euklidischer Algorithmus"