Größten gemeinsamen Teiler (ggT/GCD) von zwei oder mehr Zahlen berechnen
Der größte gemeinsame Teiler (ggT), auch als GCD (Greatest Common Divisor) oder HCF (Highest Common Factor) bezeichnet, ist die größte positive ganze Zahl, die zwei oder mehr Zahlen ohne Rest teilt. Zum Beispiel ist der ggT von 12 und 18 gleich 6.
Der ggT ist grundlegend für das Kürzen von Brüchen, das Lösen von Verhältnisproblemen und die Zahlentheorie. Wenn Sie einen Bruch wie 12/18 auf 2/3 kürzen, dividieren Sie Zähler und Nenner durch ihren ggT (6).
Es gibt mehrere Methoden zur Berechnung des ggT: das Auflisten aller Teiler, die Primfaktorzerlegung oder der effiziente euklidische Algorithmus. Der euklidische Algorithmus, der über 2.300 Jahre alt ist, bleibt die schnellste Methode für große Zahlen.
Alle Teiler jeder Zahl aufzählen, gemeinsame finden, den größten auswählen.
Jede Zahl in Primfaktoren zerlegen, gemeinsame Primfaktoren multiplizieren.
ggT(a,b) = ggT(b, a mod b) wiederholt anwenden, bis der Rest 0 ist.
Größere durch kleinere Zahl teilen, Rest weiter verwenden, bis Null erreicht ist.
Referenztabelle für häufig benötigte ggT-Berechnungen:
| Zahlen | ggT | Gemeinsame Teiler | kgV |
|---|---|---|---|
| 12, 18 | 6 | 1, 2, 3, 6 | 36 |
| 24, 36 | 12 | 1, 2, 3, 4, 6, 12 | 72 |
| 15, 25 | 5 | 1, 5 | 75 |
| 48, 60 | 12 | 1, 2, 3, 4, 6, 12 | 240 |
| 100, 75 | 25 | 1, 5, 25 | 300 |
| 8, 12, 20 | 4 | 1, 2, 4 | 120 |
Zähler und Nenner durch den ggT dividieren, um auf den kleinsten Term zu kürzen. 24/36 → durch ggT(24,36)=12 dividieren → 2/3.
Die größte quadratische Fliese finden, die einen Boden gleichmäßig ausfüllt. Für einen 12 × 18 Fuß großen Raum verwendet man 6 × 6 Fuß große Fliesen (ggT = 6).
Gegenstände gleichmäßig aufteilen. Mit 24 Äpfeln und 36 Orangen lassen sich ggT(24,36)=6 identische Geschenktüten zusammenstellen.
Zahnradübersetzungen mit dem ggT vereinfachen. Ein Verhältnis von 48:32 vereinfacht sich zu 3:2 (durch ggT=16 dividieren).
Der ggT ist die größte Zahl, die alle gegebenen Zahlen teilt. Das kgV ist die kleinste Zahl, die durch alle gegebenen Zahlen teilbar ist. Sie stehen in Beziehung zueinander: ggT × kgV = Produkt der beiden Zahlen.
Zahlen, die außer 1 keinen gemeinsamen Teiler haben, nennt man teilerfremd oder relativ prim. Ihr ggT ist 1. Beispiele: 8 und 15, 9 und 14.
Berechnen Sie den ggT der ersten beiden Zahlen, dann den ggT dieses Ergebnisses mit der dritten Zahl und so weiter. ggT(12, 18, 24) = ggT(ggT(12,18), 24) = ggT(6, 24) = 6.
Nein. Der ggT ist immer kleiner oder gleich der kleinsten Zahl. Da der ggT beide Zahlen teilt, kann er keine von beiden überschreiten.
Berechnen Sie den größten gemeinsamen Teiler von 24 und 36 mit dem euklidischen Algorithmus und überprüfen Sie das Ergebnis anschließend mit der ggT-kgV-Beziehung.
ErgebnisggT(24, 36) = 12
Schritt 1: 36 mod 24 = 12, also ggT(24, 36) = ggT(24, 12). Schritt 2: 24 mod 12 = 0, also ggT(24, 12) = 12. Probe: ggT × kgV = a × b → 12 × 72 = 864 = 24 × 36.
Der ggT zweier oder mehrerer ganzer Zahlen ist die größte positive ganze Zahl, die jede dieser Zahlen ohne Rest teilt. So ist ggT(24, 36) = 12, weil 12 sowohl 24 als auch 36 ohne Rest teilt und keine größere Zahl diese Eigenschaft besitzt.
Der euklidische Algorithmus ersetzt das Paar (a, b) wiederholt durch (b, a mod b), bis der Rest 0 ist. Der letzte von Null verschiedene Rest ist der ggT. Das Verfahren benötigt nur O(log min(a, b)) Schritte und ist damit deutlich schneller als das Aufzählen aller Teiler.
Zerlegen Sie jede Zahl in ihre Primfaktoren und multiplizieren Sie die in allen Zerlegungen vorkommenden Primfaktoren mit dem jeweils kleinsten Exponenten. Beispiel: 24 = 2^3 · 3 und 36 = 2^2 · 3^2; gemeinsam sind 2^2 und 3, also ggT = 4 · 3 = 12.
Wenn Sie Zähler und Nenner eines Bruchs durch ihren ggT dividieren, erhalten Sie den vollständig gekürzten Bruch. Für 24/36 ist ggT(24, 36) = 12, somit 24/36 = 2/3. Einmaliges Kürzen mit dem ggT ersetzt mehrere Einzelkürzungen.
Zwei ganze Zahlen heißen teilerfremd (oder relativ prim), wenn ihr ggT gleich 1 ist, sie also keinen gemeinsamen Primfaktor besitzen. Beispiele sind 8 und 15 oder 14 und 25. Teilerfremde Paare spielen eine Rolle in der Bruchrechnung, der modularen Arithmetik und der Kryptografie.
Der ggT erscheint überall dort, wo Mengen in gleich große Gruppen aufgeteilt, Flächen mit größtmöglichen gleichen Quadraten ausgelegt, Übersetzungs- oder Seitenverhältnisse vereinfacht oder periodische Abläufe synchronisiert werden. Außerdem ist er Grundlage in der Bruchrechnung sowie in Algorithmen der Kryptografie wie der RSA-Schlüsselerzeugung.
Der Rechner nutzt die Eigenschaft ggT(a, b, c) = ggT(ggT(a, b), c) und wendet den euklidischen Algorithmus nacheinander auf die gesamte Liste an. Damit lassen sich beliebig viele positive ganze Zahlen mit derselben Effizienz verarbeiten.
Fanden Sie diesen Rechner hilfreich? Teilen Sie ihn:
