Größter gemeinsamer Teiler
| Algorithmus | aus dem mathematischen Teilgebiet der Zahlentheorie |
| Anwendung | zur Ermittlung des größten gemeinsamen Teilers ggT |
| benannt nach | Euklid 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:
- Größere durch kleinere Zahl teilen – Rest notieren
- Divisor durch den vorher notierten Rest teilen
- So lange durchführen bis kein Rest übrig ist
- 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!
