Euklidischer Algorithmus - ggT Beispiel

Euklidischer Algorithmus

Der Euklidischer Algorithmus lässt sich anwenden, um den größten gemeinsamen Teiler - ggT - von zwei natürlichen Zahlen zu bestimmen und zu berechnen.

Größter gemeinsamer Teiler

Algorithmusaus dem mathematischen Teilgebiet der Zahlentheorie
Anwendungzur Ermittlung des größten gemeinsamen Teilers ggT
benannt nachEuklid von Alexandira ~ 3. Jahrhundert v. Chr.

Der Euklidischer Algorithmus

Der Euklidischer Algorithmus lässt sich anwenden, um den größten gemeinsamen Teiler von zwei natürlichen Zahlen zu berechnen.

Wenn der ggT gleich eins ist, sind die Zahlen allerdings teilerfremd – der einzige gemeinsame Teiler ist die Eins.

Siehe auch: Summenregel der Teilbarkeitsrelation.

Ablauf

Der euklidische Algorithmus wird in drei Schritten durchgeführt:

  1. Größere durch kleinere Zahl teilen – Rest notieren
  2. Divisor durch den vorher notierten Rest teilen
    1. So lange durchführen bis kein Rest übrig ist
  3. Ergebnis notieren als ggT(a|b)=x

Beispiel der Teiler

Der größte gemeinsame Teiler von 66 und 156 wird gesucht.

\(
\begin{Bmatrix}
a & q & b & r \\
156= & 2* & {\color{Red} 6}{\color{Red} 6} & {\color{Green} +}{\color{Green} 2}{\color{Green} 4} \\
{\color{Red} 6}{\color{Red} 6}= & 2* & {\color{Green} 2}{\color{Green} 4} & {\color{Magenta} +}{\color{Magenta} 1}{\color{Magenta} 8} \\
{\color{Green} 2}{\color{Green} 4}= & 1* & {\color{Magenta} 1}{\color{Magenta} 8} & +\textbf{6} \\
{\color{Magenta} 1}{\color{Magenta} 8}= & 3* & \textbf{6} & +0
\end{Bmatrix}
\)

ggT(156,66)=6

Erklärung zum Beispiel

a und b stehen für die beiden Zahlen, von denen der Teiler gesucht wird – als Platzhalter

q als Faktor und r als Rest.

Dies kann auch verkürzt dargestellt werden ohne Zeichen und den Faktor q. Für das Beispiel oben würde das Ganze dann folgendermaßen aussehen:

\(\begin{Bmatrix}
a & b & r\\
156 & 66 & 24\\
66 & 24 & 18\\
24 & 18 & 6\\
18 & 6 & 0
\end{Bmatrix}\)

Die Beschriftung oben mit a, b und r dient lediglich der Orientierung und Übersicht!