Mit dem Euklidischen Algorithmus lässt sich der größte gemeinsame Teiler von zwei natürlichen Zahlen bestimmen. Darüber hinaus findet er beim Beweis des Fundamentalsatzes der Arithmetik Anwendung. Das Verfahren ist - genau wie der Satz von Euklid - nach dem berühmten griechischen Mathematiker Euklid von Alexandria benannt.
Seien \(a, b \in \mathbb{Z}\) mit \(a \not = 0\). Dann existieren eindeutig bestimmte Zahlen \(q \in \mathbb{Z}\) und \(r \in \mathbb{N}_0\) mit \(b = qa + r\) und \(0 \leq r \lt |a|\).
Beweis:
Wir betrachten die Menge \(M := \{b - na|n \in \mathbb{Z}\}\). Sei \(r \in M\) die kleinste Zahl in \(M\), für die gilt \(r \geq 0\). Dann gibt es ein \(q \in \mathbb{Z}\) mit \(r = b - qa \Leftrightarrow b = qa + r\). Offensichtlich ist \(r \in \mathbb{N}_0\).
Als nächstes zeigen wir, dass \(r \lt |a|\) ist. Diese Aussage beweisen wir durch einen Widerspruch: Angenommen, es wäre \(r \geq |a|\). Dann ist \(r - |a| \geq 0\). Aus \(r \in M\) folgt, dass auch \(r - |a| \in M\) ist. Dies führt zu einem Widerspruch, denn es ist \(r \gt r - |a|\), aber wir hatten \(r\) als die kleinste nichtnegative Zahl in \(M\) gewählt. Somit muss gelten \(0 \leq r \lt |a|\).
Abschließend bleibt noch die Eindeutigkeit der Zahlen \(q\) und \(r\) zu zeigen. Seien hierzu \(q' \in \mathbb{Z}\) und \(r' \in \mathbb{N}_0\) mit \(b = q'a + r'\) und \(0 \leq r' \lt |a|\). Angenommen, es wäre \(r' \not = r\). Dann ist \(r' \gt r\), denn wir haben \(r\) als die kleinste nichtnegative Zahl in \(M\) gewählt. Damit gilt \(0 \lt r' - r \lt |a|\). Es gilt weiterhin \(r' - r = b - q'a - b + qa = (q - q')a\). Folglich ist \(a\) ein Teiler von \(r' - r\). Damit ist auch \(|a|\) ein Teiler von \(r' - r\). Dies ist jedoch ein Widerspruch, da wir vorher gezeigt haben, dass \(|a| \gt r' - r \gt 0\) ist. Folglich ist die Annahme \(r' \not = r\) falsch und es muss \(r' = r\) gelten. Daraus folgt \(b = qa + r = q'a + r\) und somit muss \(q' = q\) gelten. \(\square\)
Beispiel: Division mit Rest
Seien \(a = 17\) und \(b = 5\). Dann ist \(17 = 3 \cdot 5 + 2\), also \(q = 3\) und \(r = 2\).
Seien \(a = 1029\) und \(b = 42\). Dann ist \(1029 = 24 \cdot 42 + 21\), also \(q = 24\) und \(r = 21\).
Seien \(a = 98\) und \(b = 14\). Dann ist \(98 = 7 \cdot 14 + 0\), also \(q = 7\) und \(r = 0\).
Seien \(a = 11\) und \(b = 15\). Dann ist \(11 = 0 \cdot 15 + 11\), also \(q = 0\) und \(r = 11\).
Die Division mit Rest wird uns später bei der Durchführung des Euklidischen Algorithmus wieder begegnen. Vorher wollen wir noch definieren, was wir unter dem größten gemeinsamen Teiler zweier Zalen verstehen.
Seien \(a, b \in \mathbb{Z}\) mit \(a \not = 0\). Eine natürliche Zahl \(n \in \mathbb{N}\) heißt größter gemeinsamer Teiler von \(a\) und \(b\) (geschrieben als \(ggT(a, b)\)), wenn gilt:
Der größte gemeinsame Teiler (ggT) zweier Zahlen \(a\) und \(b\) teilt als zum einen diese beiden Zahlen, zum anderen wird er selbst von jeder ganzen Zahl geteilt, die ebenfalls diese beiden Zahlen teilt. Es ist zu beachten, dass der größte gemeinsame Teiler zweier Zahlen per Definition immer eine natürliche Zahl, also insbesondere immer positiv, ist.
Beispiel: Größter gemeinsamer Teiler
Seien \(a := 1071\) und \(b := 1029\). Ohne Anwendung des Euklidischen Algorithmus könnten wir den größten gemeinsamen Teiler z.B. durch einen Vergleich der Teilermengen bestimmen. Hierzu ermitteln wir zunächst diejenigen natürlichen Zahlen, die sowohl \(a\) als auch \(b\) teilen. Dies sind 1, 3, 7 und 21. Es existieren noch weitere Zahlen, die entweder nur \(a\) oder nur \(b\) teilen. Da wir jedoch auf der Suche nach dem größten gemeinsamen Teiler sind, sind diese Zahlen nicht relevant. Die Zahlen 1, 3 und 7 können jeweils keine größten gemeinsamen Teiler von \(a\) und \(b\) sein, denn sie werden nicht von 21 geteilt. Der größte gemeinsame Teiler ist somit 21, denn \(21|a\) und \(21|b\) und 21 selbst wird jeweils von 1, 3 und 7 geteilt.
Eine weitere Möglichkeit, den größten gemeinsamen Teiler von \(a\) und \(b\) zu bestimmen, wäre die Primfaktorzerlegung. Es ist \(1071 = 3 \cdot 3 \cdot 7 \cdot 17 = 3^2 \cdot 7 \cdot 17\) und \(1029 = 3 \cdot 7 \cdot 7 \cdot 7 = 3 \cdot 7^3\). Man betrachtet nun die Primfaktoren, die in beiden Zerlegungen vorkommen, in diesem Beispiel also 3 und 7, sowie deren Häufigkeiten in den Primfaktorzerlegungen. Der größte gemeinsame Teiler berechnet sich dann als Produkt dieser Faktoren, mit der kleineren der beiden Häufigkeiten als Exponent. Da der Faktor 3 in der Primfaktorzerlegung von 1029 nur einmal vorkommt, ist der entsprechende Exponent für diesen Faktor 1. Entsprechendes gilt für den Faktor 7, der in 1071 nur einmal vorkommt. Der größte gemeinsame Teiler ergibt sich somit zu \(3^1 \cdot 7^1 = 21\).
Obwohl man mit diesen Vorgehensweisen prinzipiell den größten gemeinsamen Teiler von zwei Zahlen ermitteln kann, sind beide Verfahren insbesondere für große Zahlen sehr aufwendig. Mit dem Euklidischen Algorithmus ist die Bestimmung des größten gemeinsamen Teilers für alle ganzen Zahlen \(\mathbb{Z}\) weitaus effizienter möglich.
Bevor wir diesen Algorithmus im Detail vorstellen, wollen wir zunächst kurz darlegen, warum es korrekt ist, von "dem" größten Teiler zweier Zahlen zu sprechen.
Seien \(a, b \in \mathbb{Z}\) mit \(a, b \not = 0\). Dann ist der größte gemeinsame Teiler von \(a\) und \(b\) eindeutig bestimmt.
Beweis:
Seien \(n_1\) und \(n_2\) größte gemeinsame Teiler von \(a\) und \(b\). Wir müssen zeigen, dass dann \(n_1 = n_2\) gilt.
Angenommen, es wäre \(n_1 \not = n_2\). Dann ist entweder \(n_1 \gt n_2\) oder \(n_2 \gt n_1\). Ohne Beschränkung der Allgemeinheit können wir annehmen, dass \(n_1 \gt n_2\) gilt. Nach Definition des größten gemeinsamen Teilers gilt aber \(n_1|n_2\) (denn \(n_2\) ist größter gemeinsamer Teiler von \(a\) und \(b\) und wird somit von jeder anderen ganzen Zahl geteilt, die ebenfalls \(a\) und \(b\) teilt). Das ist jedoch ein Widerspruch, denn eine größere natürliche Zahl kann keine kleinere natürliche Zahl teilen. Es folgt \(n_1 = n_2\) und somit die Eindeutigkeit des größten gemeinsamen Teilers. \(\square\)
Der größte gemeinsame Teiler zweier Zahlen ist somit eindeutig. Deshalb ist es tatsächlich korrekt, von "dem" größten gemeinsamen Teiler zu sprechen (anstatt von "einem").
Seien \(a, b \in \mathbb{N}\). Dann sind \(a\) und \(b\) genau dann teilerfremd, wenn \(ggT(a, b) = 1\) ist.
Beweis:
\(\Rightarrow\): Seien \(a\) und \(b\) teilerfremd. Dann lassen sich \(a\) und \(b\) gemäß dem Fundamentalsatz der Algebra in eindeutiger Weise als Produkt von Primzahlen schreiben, die keinen einzigen Faktor gemeinsam haben. Demnach existiert kein \(n \in \mathbb{N}, n \gt 1\) mit \(n|a\) und \(n|b\). Somit ist \(ggT(a, b) = 1\).
\(\Leftarrow\): Sei \(ggT(a, b) = 1\). Angenommen, \(a\) und \(b\) wären nicht teilerfremd. Dann gibt es gemäß dem Fundamentalsatz der Algebra eine Primzahl \(p\) mit \(p|a\) und \(p|b\). Somit ist \(p\) ein gemeinsamer Teiler von \(a\) und \(b\). Entweder ist \(p\) der größte gemeinsame Teiler von \(a\) und \(b\), dann gilt \(ggT(a, b) = p\). Oder es gibt ein \(m \in \mathbb{Z}\) mit \(m \geq p\) und \(ggT(a, b) = m\). In beiden Fällen führt dies zu einem Widerspruch, denn nach Voraussetzung ist \(ggT(a, b) = 1\). \(\square\)
Der nachfolgende Hilfssatz kommt bei der Durchführung des Euklidischen Algorithmus zum Einsatz und liefert eine Begründung dafür, warum dieser tatsächlich korrekt funktioniert.
Seien \(a, b \in \mathbb{Z}\) mit \(a \not = 0\). Sei \(b = qa + r\) mit \(q \in \mathbb{Z}\) und \(0 \leq r \lt |a|\). Sei \(x \in \mathbb{N}\) der größte gemeinsame Teiler von \(a\) und \(r\), also \(ggT(a, r) = x\). Dann ist \(x\) auch der größte gemeinsame Teiler von \(a\) und \(b\), d.h. es gilt \(ggT(a, b) = ggT(a, r) = x\).
Beweis:
Sei \(x = ggT(a, r)\). Dann ist \(x\) per Definition positiv und es gilt \(x|a\) und \(x|r\). Es gibt also \(z_1, z_2 \in \mathbb{Z}\) mit \(z_1x=a\) und \(z_2x = r\). Damit ist \(b = qa + r = qz_1x + z_2x = (qz_1 + z_2)x\) und folglich gilt \(x|b\). Somit erfüllt \(x\) die erste Bedingung aus der Definition des größten gemeinsamen Teilers für \(a\) und \(b\).
Sei \(y\) ein Teiler von \(a\) und \(b\), also \(y|a\) und \(y|b\). Dann folgt mit der gleichen Argumentation wie oben, dass auch \(y|r\), denn \(r = b - qa\). Weil \(x\) der größte gemeinsame Teiler von \(a\) und \(r\) ist und dieser per Definition von jedem anderen Teiler von \(a\) und \(r\) geteilt wird, folgt damit \(y|x\). Somit erfüllt \(x\) auch die zweite Bedingung aus der Definition des größten gemeinsamen Teilers für \(a\) und \(b\) und es gilt \(ggT(a, b) = x. \square\)
Seien \(a, b \in \mathbb{Z}\) mit \(a \not = 0\). Dann lässt sich der größte gemeinsame Teiler von \(a\) und \(b\) wie folgt eindeutig bestimmen:
Wir dividieren \(b\) durch \(a\) mit Rest und erhalten \(b = q_1a + r_1\) mit \(0 \leq r_1 \leq |a|\).
Falls \(r_1 = 0\) ist, so ist \(|a| = ggT(a, 0)\) und mit dem vorangegangenen Lemma gilt \(ggT(a, b) = ggT(a, r_1) = ggT(a, 0) = |a|\).
Falls \(r_1 \not = 0\) ist, dividieren wir \(a\) durch \(r_1\) mit Rest und erhalten \(a = q_2r_1 + r_2\) mit \(0 \leq r_2 \lt r_1\).
Falls \(r_2 = 0\) ist, so ist \(r_1 = ggT(r_1, 0)\) und mit dem vorangegangenen Lemma gilt \(ggT(a, b) = ggT(a, r_1) = ggT(r_1, r_2) = ggT(r_1, 0) = r_1\).
Falls \(r_2 \not = 0\) ist, dividieren wir \(r_1\) durch \(r_2\) mit Rest und setzen das Verfahren in dieser Weise fort, bis der Rest irgendwann \(0\) ist.
Wir erhalten dadurch eine absteigende Folge von Restwerten \(|a| \gt r_1 \gt r_2 \gt \dots \gt r_n \gt r_{n+1} = 0\). Da es nur endlich viele ganze Zahlen zwischen \(|a|\) und \(0\) gibt, ist sichergestellt, dass das Verfahren irgendwann terminiert. Auf diese Weise erhalten wir eine Reihe von Gleichungen der Form: \[b = q_1a + r_1 \text{, mit } 0 \lt r_1 \lt |a|\] \[a = q_2r_1 + r_2 \text{, mit } 0 \lt r_2 \lt r_1\] \[r_1 = q_3r_2 + r_3 \text{, mit } 0 \lt r_3 \lt r_2\] \[\vdots\] \[r_{n-2} = q_nr_{n-1} + r_n \text{, mit } 0 \lt r_n \lt r_{n-1}\] \[r_{n-1} = q_{n+1}r_n\]
Mit dem vorangegangenen Lemma gilt dann \(r_n = ggT(r_n, 0) = ggT(r_{n-1}, r_n) = \dots = ggT(a, r_1) = ggT(a, b)\).
Beispiel: Euklidischer Algorithmus
Seien wie im vorangegangenen Beispiel \(a := 1071\) und \(b := 1029\). Diesmal wollen wir den größten gemeinsamen Teiler der beiden Zahlen mithilfe des Euklidischen Algorithmus berechnen. Es ist: \[1071 = 1 \cdot 1029 + 42\] \[1029 = 24 \cdot 42 + 21\] \[42 = 2 \cdot 21 + 0\]
Der größte gemeinsame Teiler von 1071 und 1029 ist somit \(ggT(1071, 1029) = 21\).
Ein weiteres Beispiel, an dem überdies deutlich wird, dass die Reihenfolge der Zahlen keine Rolle spielt, man also auch die kleinere der beiden Zahlen durch die größere dividieren darf (wodurch man allerdings im Endeffekt einen Rechenschritt zusätzlich durchführen muss): Seien \(c := 64\) und \(d := 310\). Dann ist: \[64 = 0 \cdot 310 + 64\] \[310 = 4 \cdot 64 + 54\] \[64 = 1 \cdot 54 + 10\] \[54 = 5 \cdot 10 + 4\] \[10 = 2 \cdot 4 + 2\] \[4 = 2 \cdot 2 + 0\]
Der größte gemeinsame Teiler von 64 und 310 ist somit \(ggT(64, 310) = 2\).
Mit dem Euklidischen Algorithmus können wir insbesondere auch dann den größten gemeinsamen Teiler bestimmen, wenn eine oder beide Zahlen negativ sind. Seien z.B. \(e := -2002\) und \(f := 210\). Dann ist: \[-2002 = -10 \cdot 210 + 98\] \[210 = 2 \cdot 98 + 14\] \[98 = 7 \cdot 14 + 0\]
Somit gilt \(ggT(-2002, 210) = 14\).
Es gilt in jenen Fällen, in denen negative Zahlen beteiligt sind, stets darauf zu achten, dass der Rest immer eine nichtnegative Zahl sein muss! Wir hätten -2002 auch als \(-2002 = -9 \cdot 210 + (-112)\) darstellen können, allerdings wäre der Rest dann -112 und damit eine negative Zahl gewesen. Dieser Rechenweg hätte nicht zu einem korrekten Ergebnis geführt.
Der größte gemeinsame Teiler zweier Zahlen kann auch 1 sein. Dies ist dann der Fall, wenn beide Zahlen keine gemeinsamen Primteiler besitzen. Für \(g := 78\) und \(h := 35\) gilt beispielsweise: \[78 = 2 \cdot 35 + 8\] \[35 = 4 \cdot 8 + 3\] \[8 = 2 \cdot 3 + 2\] \[3 = 1 \cdot 2 + 1\] \[2 = 2 \cdot 1 + 0\] also \(ggT(78, 35) = 1\).