Buchempfehlung vom Abi-Physik Team
Metzler Physik Sekundarstufe II - 3. Auflage
Mehr Informationen bei Amazon

Euklidischer Algorithmus

Einige Videos sind leider bis auf weiteres nicht verfügbar.

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

Abi-Mathe © 2017, Partner: Abi-Mathe, Abi-Chemie,