1.5. Größter gemeinsamer Teiler (ggT)#
Der größte gemeinsamer Teiler (ggT) ist ein mathematischer Begriff und bezeichnet die gemeinsame größte natürliche Zahl, durch welche sich zwei Zahlen ohne Rest teilen lassen. In dieser Aufgabe wird ein Algorithmus zum finden des ggT vorgestellt und angewandt. So ist bspw. der ggT von \(12\) und \(18\), die Zahl \(6\). Der ggT wird unter anderem in der Bruchrechnung verwendet, beim Kürzen eines Bruches.
Die Bestimmung des ggT kann durch eine Primfaktorzerlegung oder durch den euklidischen Algorithmus erfolgen. Nachfolgend wird die Primfaktorzerlegung genutzt. Bei der Primfaktorzerlegung werden, wie der Name schon sagt, die Zahl in ein Produkt aus Primzahlen zerlegt.
Bsp.:
\(12 = 2^{\color{red}2} \cdot 3^{\color{red}1}\)
\(18 = 2^{\color{green}1} \cdot 3^{\color{green}2} \)
Mit Hilfe der Primfaktorzerlegung lässt sich nun einfach ablesen, was der ggT von \(12\) und \(18\) ist, indem man die Primfaktoren miteinander multipliziert, die in beiden Zerlegungen vorkommen. In diesem Fall kommen sowohl \(2\) als auch \(3\) einmal in beiden Zerlegungen vor und damit ist der ggT \(2^{\color{green}1} \cdot 3^{\color{red}1} = 6\). Nachfolgend ist ein Algorithmus aufgeführt, der die Bestimmung des ggT formalisiert.
Algorithmus zur Bestimmung des ggT:#
Bestimme die Primfaktorzerlegung für beide Zahlen.
A. Starte mit der kleinsten Primzahl.
B. Teile die erste Zahl wiederholt durch diese Primzahl, bis sie sich nicht mehr ganzzahlig durch diese teilen lässt und notiere, wie oft diese Division durchgeführt wurde.
C. Wechsel zur nächst größeren Primzahl.
D. Wiederhole die vorherigen Schritt B und C, nur anstelle der ursprünglichen Zahl, nimm das Ergebnis der vorherigen Rechnung als neuen Start für die Division. Tue dies, solange das Ergebnis größer 1 ist.
E. Wiederhole die Schritte A-D für die zweite Zahl.Potenziere jede Primzahl mit der kleineren der beiden notierten Anzahlen ganzzahliger Divisionen.
Multipliziere die errechneten Ergebnisse aus Schritt 2, um den ggT zu erhalten.
Eine einfache Möglichkeit die Ergebnisse aus Schritt 1.B und 2 aufzuschreiben, wäre beispielweise in Form einer Tabelle:
Primzahlen |
Zahl1 |
Zahl2 |
Ergebnis |
|---|---|---|---|
2 |
… |
… |
… |
3 |
… |
… |
… |
5 |
… |
… |
… |
… |
… |
… |
… |
Beispiel:#
Primfaktorzerlegung von 20: Zu Lesezwecken ist p die Primzahl und x (=20) die zu zerteilende Zahl.
A. p = 2
B. x (20) ist durch p (2) zweimal ohne Rest teilbar, das neue x ist jetzt \(x = 20 / 2 / 2 = 5\)
C. Wechsel zur nächsten Primzahl p = 3
D. x (5) ist nicht 1, also Schritt B und C wiederholen
B. x (5) ist durch p (3) keinmal ohne Rest teilbar, x bleibt 5
C. Wechsel zur nächsten Primzahl p = 5
D. x (5) ist nicht 1, also Schritt B und C wiederholen
B. x (5) ist durch p (5) einmal ohne Rest teilbar, \(x = 5/5 = 1\)
C. Wechsel zur nächsten Primzahl p = 7
D. x ist 1, somit ist die Primfaktorzerlegung abgeschlossen
Die daraus resultierende Ergebnisse, eingetragen in einer Tabelle, sähen so aus:
Primzahlen |
20 |
|---|---|
2 |
2 |
3 |
0 |
5 |
1 |
Aufgabenstellung#
Führen Sie den Algorithmus zur Bestimmung des ggT von 315 und 126 Schritt für Schritt aus und notieren Sie Ihre Ergebnisse in einer Tabelle.
Testen Sie Ihr Ergebnis, indem Sie die beiden Zahlen durch den ggT teilen. Sollte bei einer der beiden Divisionen ein Rest bleiben, überprüfen Sie deren Primfaktorzerlegung. Sollte Ihr ggT beide Zahlen teilen, aber es nicht der größte gemeinsame Teiler sein, überprüfen Sie, ob bei Schritt 2 eine Zahl falsch übertragen wurde oder bei Schritt 3 bei der Multiplikation eine Zeile übersehen wurde.
Lösungshinweise#
Sie können Ihre Ergebnisse nach Schritt 1 kontrollieren indem Sie die Zahlen wieder miteinander multiplizieren. Die Zahlen der Spalte sollten entsprechend wieder ihre Ursprungszahl ergeben.
Primzahlen |
20 |
|---|---|
2 |
2 |
3 |
0 |
5 |
1 |
Kontrolle: \(2^2 \cdot 3^0 \cdot 5^1 = 20\)
Lösungsvorschlag#
Nach der Primfaktorzerlegung sieht die Tabelle folgendermaßen aus:
Primzahlen |
315 |
126 |
|---|---|---|
2 |
0 |
1 |
3 |
2 |
2 |
5 |
1 |
0 |
7 |
1 |
1 |
\(315 = 2^{\color{red}0} \cdot 3^{\color{red}2} \cdot 5^{\color{red}1} \cdot 7^{\color{red}1}\) oder alternativ \(315 = 3^2 \cdot 5^1 \cdot 7^1\)
\(126 = 2^{\color{green}1} \cdot 3^{\color{green}2} \cdot 5^{\color{green}0} \cdot 7^{\color{green}1}\) oder alternativ \(126 = 2^1 \cdot 3^2 \cdot 7^1\)
Die aus Schritt 2 resultierende Tabelle sähe so aus.
Primzahlen |
315 |
126 |
Ergebnis |
|---|---|---|---|
\(2\) |
\(0\) |
\(1\) |
\(2^0\) |
\(3\) |
\(2\) |
\(2\) |
\(3^2\) |
\(5\) |
\(1\) |
\(0\) |
\(5^0\) |
\(7\) |
\(1\) |
\(1\) |
\(7^1\) |
Entsprechend ergibt sich als ggT von 315 und 126: \(2^{\color{red}0} \cdot 3^2 \cdot 5^{\color{green}0} \cdot 7^1 = 3^2 \cdot 7 = 63\)