ggT Rechner – Größter Gemeinsamer Teiler

Der ggT-Rechner ermittelt den größten gemeinsamen Teiler aus bis zu fünfzehn Zahlen. Lies weiter, um eine Antwort auf die Frage: ,,Was ist der größte gemeinsame Teiler meiner gegebenen Zahlen?“ zu finden. Lerne verschiedene Methoden zur Ermittlung des ggT kennen, wie z. B. die Primfaktorzerlegung oder den euklidischen Algorithmus; entscheide dich für deine Lieblingsmethode und überprüfe selbst, ob unser ggT-Rechner dir beim Umgang mit großen Zahlen Zeit sparen kann!

Der größte gemeinsame Teiler ist der größte ganzzahlige Faktor, der in einer Gruppe von Zahlen vorhanden ist. Das ist bei bestimmten mathematischen Anwendungen von Bedeutung, z. B. bei der Vereinfachung von Polynomen, bei denen es wichtig ist, gemeinsame Faktoren herauszuziehen. Als Nächstes müssen wir wissen, wie man den ggT findet.

Es gibt verschiedene Methoden, die dir helfen, den ggT zu finden. Einige davon sind kinderleicht, während andere komplexer sind. Es empfiehlt sich, alle davon zu kennen, damit du selbst entscheiden kannst, welche dir am liebsten ist:

• Auflistung der Divisoren;
• Primfaktorzerlegung von Zahlen;
• Euklidischer Algorithmus;
• Binärer Algorithmus (Steinscher Algorithmus); und
• Verwendung mehrerer Eigenschaften von ggT (einschließlich des kleinsten gemeinsamen Vielfachen, kgV).

Die gute Nachricht ist, dass du den ggT mit einfachen mathematischen Operationen ohne Wurzeln oder Logarithmus schätzen kannst! In den meisten Fällen handelt es sich nur um Subtraktion, Multiplikation oder Division.

Die wichtigste Methode zur Ermittlung des größten gemeinsamen Teilers besteht darin, alle Divisoren 🇺🇸 der gegebenen Zahlen zu finden. Divisoren sind in diesem Fall lediglich die Zahlen, durch die unser Wert ohne Rest geteilt werden kann. Im Allgemeinen können sie sowohl positiv als auch negativ sein, z. B. ist 2 ∙ 3 dasselbe wie (-2) ∙ (-3), beides ergibt 6. Aus praktischer Sicht betrachten wir nur positive und ganze Zahlen. Andernfalls könnte man eine unendliche Kombination von verschiedenen Brüchen als Faktoren finden, was in unserem Fall sinnlos ist. Schätzen wir also den größten gemeinsamen Teiler der Zahlen 72 und 40.

1. Die Divisoren von 72 sind: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
2. Die Divisoren von 40 sind: 1, 2, 4, 5, 8, 10, 20, 40.
3. Listen wir alle gemeinsamen Divisoren auf: 1, 2, 4, 8.
4. Der größte gemeinsame Divisor ist 8, also der höchste Wert.

Versuchen wir es mit einer größeren Herausforderung. Wir möchten eine Antwort auf die Frage: „Was ist der größte gemeinsame Teiler von 33 264 und 35 640?“, finden. Alles, was wir tun müssen, ist, die vorherigen Schritte zu wiederholen:

1. Die Divisoren von 33 264 sind: 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 21, 22, 24, 27, 28, 33, 36, 42, 44, 48, 54, 56, 63, 66, 72, 77, 84, 88, 99, 108, 112, 126, 132, 144, 154, 168, 176, 189, 198, 216, 231, 252, 264, 297, 308, 336, 378, 396, 432, 462, 504, 528, 594, 616, 693, 756, 792, 924, 1008, 1188, 1232, 1386, 1512, 1584, 1848, 2079, 2376, 2772, 3024, 3696, 4158, 4752, 5544, 8316, 11 088, 16 632, 33 264.

2. Die Divisoren von 35 640 sind: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 18, 20, 22, 24, 27, 30, 33, 36, 40, 44, 45, 54, 55, 60, 66, 72, 81, 88, 90, 99, 108, 110, 120, 132, 135, 162, 165, 180, 198, 216, 220, 264, 270, 297, 324, 330, 360, 396, 405, 440, 495, 540, 594, 648, 660, 792, 810, 891, 990, 1080, 1188, 1320, 1485, 1620, 1782, 1980, 2376, 2970, 3240, 3564, 3960, 4455, 5940, 7128, 8910, 11 880, 17 820, 35 640.

3. Liste aller gemeinsamen Divisoren: 1, 2, 3, 4, 6, 8, 9, 11, 12, 18, 22, 24, 27, 33, 36, 44, 54, 66, 72, 88, 99, 108, 132, 198, 216, 264, 297, 396, 594, 792, 1188, 2376.

4. Das Endergebnis ist: 2376.

Wie du siehst, wird das Verfahren umso zeitaufwändiger, je höher die Anzahl der Divisoren ist, und es schleichen sich schneller Fehler ein. Es ist nützlich zu verstehen, wie diese Methode funktioniert. Dennoch empfehlen wir die Verwendung unseres ggT-Rechners, um sicherzustellen, dass das Ergebnis korrekt ist.

Ein weiteres häufig verwendetes Verfahren ist die Primfaktorzerlegung 🇺🇸. Diese Methode ist in gewisser Weise mit der zuvor erwähnten Methode verwandt. Anstatt alle möglichen Divisoren aufzulisten, finden wir nur die, die Primzahlen sind. Daher ist das Produkt aller gemeinsamen Primzahlen die Antwort auf unser Problem, und was noch wichtiger ist: Es gibt immer einen einzigen Weg, jede Zahl in Primzahlen zu faktorisieren. Lass uns den größten gemeinsamen Teiler von 72 und 40 mithilfe der Primfaktorzerlegung finden:

1. Die Primfaktoren von 72 sind: 2, 2, 2, 3, 3.

2. Die Primfaktoren von 40 sind: 2, 2, 2, 5.

3. Mit anderen Worten: 72 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 3 und 40 = 2 ∙ 2 ∙ 2 ∙ 5.

4. Der gemeinsame Teil ist: 2 ∙ 2 ∙ 2 = 8 — das ist der größte gemeinsame Teiler.

Wir sehen, dass das Ergebnis für dieses einfache Beispiel mit der vorherigen Methode übereinstimmt. Lass uns herausfinden, ob sie für den komplizierteren Fall genauso gut funktioniert. Wie lautet der ggT von 33 264 und 35 640?

1. Die Primfaktoren von 33 264 sind: 2, 2, 2, 2, 3, 3, 3, 7, 11.

2. Die Primfaktoren von 35 640 sind: 2, 2, 2, 3, 3, 3, 3, 5, 11.

3. Wir können die Exponenten-Schreibweise verwenden, um die Produkte wie folgt zu schreiben: 35 640 = 2⁴ ∙ 3³ ∙ 7 ∙ 11 und 35 640 = 2³ ∙ 3⁴ ∙ 5 ∙ 11.

4. Das gemeinsame Produkt von zwei Zahlen ist 2³ ∙ 3³ ∙ 11. Wir können es auch auf eine kompaktere und anspruchsvollere Weise schreiben, indem wir die Faktoren berücksichtigen: (3!)³ ∙ 11. Prüfe, ob unser ggT-Rechner das gleiche Ergebnis liefert, nämlich 2376.

Die Idee, die dem euklidischen Algorithmus zugrunde liegt, besagt: Wenn die Zahl k der größte gemeinsame Teiler der Zahlen A und B ist, dann ist k auch der ggT für die Differenz dieser Zahlen A - B. Wenn wir so vorgehen, kommen wir schließlich auf 0. Der größte gemeinsame Divisor ist also die letzte Zahl, die nicht Null ist. Schauen wir uns unsere Beispiele noch einmal an — die Zahlen 40 und 72. Jedes Mal, wenn wir eine Subtraktion durchführen, vergleichen wir zwei Zahlen und ordnen sie vom höchsten zum kleinsten Wert:

• ggT von 72 und 40: 72 - 40 = 32;
• ggT von 40 und 32: 40 - 32 = 8;
• ggT von 32 und 8: 32 - 8 = 24;
• ggT von 24 und 8: 24 - 8 = 16;
• ggT von 16 und 8: 16 - 8 = 8;
• ggT von 8 und 8: 8 - 8 = 0 STOPP!

In letzten Schritt erhalten wir 0 durch Subtraktion. Das bedeutet, dass sich unser größter gemeinsamer Teiler im vorherigen Rechenschritt befindet: 8.

Schauen wir uns auch hier den schwierigeren Fall für die Zahlen 33 264 und 35 640 an! Versuchen wir, den ggT mit dem euklidischen Algorithmus zu finden:

• ggT von 35 640 und 33 264: 35 640 - 33 264 = 2376;
• ggT von 33 264 und 2376: 33 264 - 2376 = 30 888;
• ggT von 30 888 und 2376: 30 888 - 2376 = 28 512;
• ggT von 28 512 und 2376: 28 512 - 2376 = 26 136;
• ggT von 26 136 und 2376: 26 136 - 2376 = 23 760;
• ggT von 23 760 und 2376: 23 760 - 2376 = 21 384;
• ggT von 21 384 und 2376: 21 384 - 2376 = 19 008;
• ggT von 19 008 und 2376: 19 008 - 2376 = 16 632;
• ggT von 16 632 und 2376: 16 632 - 2376 = 14 256;
• ggT von 14 256 und 2376: 14 256 - 2376 = 11 880;
• ggT von 11 880 und 2376: 11 880 - 2376 = 9504;
• ggT von 9504 und 2376: 9504 - 2376 = 7128;
• ggT von 7128 und 2376: 7128 - 2376 = 4752;
• ggT von 4752 und 2376: 4752 - 2376 = 2376;
• ggT von 2376 und 2376: 2376 - 2376 = 0 STOPP!

Ähnlich wie im vorherigen Beispiel ist der ggT von 33 264 und 35 640 die letzte Differenz ungleich Null, also 2376.

Wie du siehst, ist die Grundversion dieses ggT-Finders sehr effizient und einfach, hat aber einen entscheidenden Nachteil. Je größer die Differenz zwischen den gegebenen Zahlen ist, desto mehr Schritte sind nötig, um den letzten Schritt zu erreichen. Der Modulo ist eine effektive Rechenoperation, die das Problem löst, da wir nur an einem Rest, der kleiner als beide Zahlen ist, interessiert sind. Wiederholen wir den euklidischen Algorithmus für unsere Beispiele, indem wir den Modulo anstelle der normalen Subtraktion verwenden:

• ggT von 72 und 40: 72 mod 40 = 32;
• ggT von 40 und 32: 40 mod 32 = 8;
• ggT von 32 und 8: 32 mod 8 = 0 STOPP!

Der größte gemeinsame Teiler ist 8. Aber was ist mit den Zahlen aus dem anderen Beispiel?

• ggT von 35 640 und 33 264: 35 640 mod 33 264 = 2376;
• ggT von 33 264 und 2376: 33 264 mod 2376 = 0 STOPP!

Der ggT von 35 640 und 33 264 ist 2376, und wir haben ihn in nur zwei statt 15 Schritten gefunden. Nicht schlecht, oder?

Wenn du Rechenoperationen magst, die einfacher als die des euklidischen Algorithmus (z. B. Modulo) sind, dann ist der binäre Algorithmus (oder Stein's Algorithmus) genau das Richtige für dich! Du brauchst nur zu vergleichen, subtrahieren und durch 2 dividieren. Wenn du den größten gemeinsamen Teiler von zwei Zahlen ermitteln möchtest, solltest du diese Identitäten beachten:

1. ggT(A, 0) = A, wir nutzen die Tatsache, dass jede Zahl durch null teilbar ist und die Beobachtung aus dem letzten Schritt des euklidischen Algorithmus — eine der Zahlen fällt auf null, somit war unser Ergebnis die vorherige Zahl.

2. Wenn sowohl A als auch B gerade sind, bedeutet das, dass ggT(A, B) = 2 ∙ ggT(A/2, B/2), da 2 ein gemeinsamer Faktor ist.

3. Wenn nur eine der Zahlen gerade ist, sagen wir A, dann ist ggT(A, B) = ggT(A/2, B). Dieses Mal ist 2 kein gemeinsamer Divisor, also können wir mit der Reduktion fortfahren, bis beide Zahlen ungerade sind.

4. Wenn sowohl A als auch B ungerade sind und A > B, dann ist ggT(A, B) = ggT((A-B)/2, B). Dieses Mal kombinieren wir zwei Merkmale in einem Schritt. Die erste ergibt sich aus dem euklidischen Algorithmus, der den größten gemeinsamen Divisor der Differenz der beiden Zahlen und der kleineren Zahl ermittelt. Zweitens ist die Division durch 2 möglich, da die Differenz zweier ungerader Zahlen gerade ist, und gemäß Schritt 3 können wir die gerade Zahl reduzieren.

5. Die Schritte 2-4 werden so lange wiederholt, bis Schritt 1 erreicht ist oder wenn A = B. Das Ergebnis ist 2ⁿ ∙ A, wobei n die Anzahl der Faktoren 2 ist, die im zweiten Schritt gefunden wurden.

Schauen wir uns das wieder an den Zahlen 40 und 72 an:

• Beides sind gerade Zahlen, also ggT(72, 40) = 2 ∙ ggT(36, 20) = 2² ∙ ggT(18, 10) = 2³ ∙ ggT(9, 5) = ...;

• Die restlichen Zahlen sind ungerade, also: ... = 2³ ∙ ggT((9-5)/2, 5) = 2³ ∙ ggT(2, 5);

• 2 ist gerade, also können wir sie reduzieren: ... = 2³ ∙ ggT(1, 5);

• 1 und 5 sind ungerade, also: ... = 2³ ∙ ggT((5-1)/2, 1) = 2³ ∙ ggT(2, 1); und

• Entferne 2 von einer geraden Zahl: ... = 2³ ∙ ggT(1, 1) = 2³ = 8.

Eigentlich hätten wir beim dritten Schritt aufhören können, denn der ggT von 1 und einer beliebigen Zahl ist 1.
Okay, und wie findet man den größten gemeinsamen Teiler von 33 264 und 35 640 mit der binären Methode?

• Zwei gerade Zahlen: ggT(35 640, 33 264) = 2 ∙ ggT(17 820, 16 632) = 2² ∙ ggT(8910, 8316) = 2³ ∙ ggT(4455, 4158) = ....

• Eine gerade und eine ungerade: ... = 2³ ∙ ggT(4455, 2079).

• Zwei ungerade: ... = 2³ ∙ ggT((4455-2079)/2, 2079) = 2³ ∙ ggT(1188, 2079).

• Eine gerade und eine ungerade: ... = 2³ ∙ ggT(594, 2079) = 2³ ∙ ggT(297, 2079).

• Zwei ungerade: ... = 2³ ∙ ggT((2079-297)/2, 297) = 2³ ∙ ggT(891, 297).

• Zwei ungerade: ... = 2³ ∙ ggT((891-297)/2, 297) = 2³ ∙ ggT(297, 297) = 2³ ∙ 297 = 2376.

Wir wissen, dass Primzahlen diejenigen sind, die nur 2 positive ganze Zahlen als Faktoren haben: 1 und sich selbst. Somit stellt sich die Frage, was teilerfremde Zahlen sind. Wir können sie als Zahlen, die keine gemeinsamen Faktoren haben, definieren. Genauer gesagt ist 1 ihr einziger gemeinsamer Faktor. Da wir die 1 bei der Primfaktorzerlegung aber weglassen, können wir auch sagen, dass sie keine gemeinsamen Divisoren haben. Mit anderen Worten: Wir können schreiben, dass die Zahlen A und B gleich groß sind, wenn ggT(A,B) = 1. Das bedeutet nicht wirklich, dass eine der beiden Zahlen eine Primzahl ist, sondern nur, dass die Liste der gemeinsamen Divisoren leer ist – sie teilerfremd sind. Beispiele für teilerfremde Zahlen sind: 5 und 7, 35 und 48, 23 156 und 44 613.

Ein lustiger Fakt: Es ist möglich, die Wahrscheinlichkeit zu berechnen, dass zwei zufällig ausgewählte Zahlen teilerfremd sind. Das ist zwar ziemlich kompliziert, aber das Gesamtergebnis liegt bei 61%. Bist du überrascht? Teste es einfach selbst — stell dir zwei zufällige Zahlen vor (sagen wir, mit mindestens 5 Ziffern), benutze unseren Rechner für den größten gemeinsamen Teiler und finde heraus, ob das Ergebnis 1 ist oder nicht. Wiederhole das Spiel mehrere Male und schätze, wie viel Prozent der gefundenen Zahlen gleich sind.

Da wir nun zahlreiche Methoden kennen, um den größten gemeinsamen Teiler von zwei Zahlen zu finden, fragst du dich vielleicht: „Wie findet man den größten gemeinsamen Teiler von drei oder mehr Zahlen?”. Es ist gar nicht so schwierig, wie es auf den ersten Blick scheinen mag. Die Auflistung aller Divisoren für jede Zahl ist definitiv eine einfache Methode, denn wir können einfach den größten Divisor finden. Allerdings merkst du schnell, dass es immer zeitaufwändiger wird, wenn die Anzahl der Zahlen steigt.

Die Methode der Primfaktorzerlegung hat einen ähnlichen Nachteil. Da wir aber alle Primzahlen z. B. in aufsteigender Reihenfolge gruppieren können, gibt es einen etwas schneller Weg zum Ergebnis als bisher.

Wenn du es hingegen vorziehst, binäre oder euklidische Algorithmen zu verwenden, um abzuschätzen, wie hoch der ggT mehrerer Zahlen ist, kannst du auch den folgenden Lehrsatz verwenden:

ggT(a, b, c) = ggT(ggT(a, b), c) = ggT(ggT(a, c), b) = ggT(ggT(b, c), a).

Das bedeutet, dass wir den ggT von zwei beliebigen Zahlen berechnen und dann den Algorithmus mit dem Ergebnis und der dritten Zahl erneut starten und so lange fortfahren können, wie noch Zahlen übrig sind. Dabei spielt es keine Rolle, welche beiden wir zuerst wählen.

Ein weiteres Konzept, das eng mit dem ggT zusammenhängt, ist das kleinste gemeinsame Vielfache. Um das kgV zu finden, gehen wir ähnlich vor wie bei der Ermittlung des ggT. Sobald wir die Zahlen auf die Primfaktorzerlegung heruntergebrochen haben, suchen wir nach der kleinsten Potenz jedes Divisors, nicht nach der größten Potenz. Dann multiplizieren wir die höchsten Potenzen, und das Ergebnis ist das kleinste gemeinsame Vielfache; kgV. Das kannst du von Hand oder mit dem kgV Rechner 🇺🇸 ermitteln.

Durch den folgenden Ausdruck kann der größte gemeinsame Teiler mithilfe des kgV geschätzt werden:

ggT(a, b) = |a ∙ b| / kgV(a, b).

Aufgrund der Komplexität und Dauer kann es praktisch sein, zuerst das kleinste gemeinsame Vielfache zu ermitteln. Natürlich kann es auf beide Arten berechnet werden, es lohnt sich also, sowohl den ggT als auch das kgV zu kennen.

Wir haben bereits ein paar Eigenschaften des größten gemeinsamen Teilers vorgestellt. In diesem Abschnitt listen wir die wichtigsten davon auf:

• Wenn das Verhältnis von zwei Zahlen a und b (a > b) eine ganze Zahl ist, dann ist ggT(a, b) = b.

• ggT(a, 0) = a, wird im euklidischen Algorithmus verwendet.

• ggT(a, 1) = 1.

• Wenn a und b keine gemeinsamen Faktoren haben (sie teilerfremd sind), dann ist ggT(a, b) = 1.

• Alle gemeinsamen Faktoren von a und b sind auch Divisoren von ggT(a,b).

• Wenn b ∙ c / a eine ganze Zahl ist und ggT(a, b) = d, dann ist auch a ∙ c / d eine ganze Zahl.

• Für jede ganze Zahl k: ggT(k∙a, k∙b) = k ∙ ggT(a, b), im binären Algorithmus verwendet.

• Für jede positive ganze Zahl k: ggT(a/k, b/k) = ggT(a, b) / k.

• ggT(a, b) ∙ kgV(a, b) = |a∙b|.

• ggT(a, kgV(b, c)) = kgV(ggT(a, b), ggT(a, c)).

• kgV(a, ggT(b, c)) = ggT(kgV(a, b), kgV(a, c)).

Nein, der ggT von 14 und 42 ist nicht 2. Der ggT von 14 und 42 ist 14. Um ihn zu finden, musst du beide Zahlen in ihre Divisoren zerlegen:

• Die Divisoren von 14 sind 1, 2, 7 und 14.
• Die Divisoren von 42 sind 1, 2, 3, 6, 7, 14, 21 und 42.

Wie du siehst, ist die größte gemeinsame Zahl aus beiden Listen 14, das ist der ggT.

Der ggT von 8 und 12 ist 4. Um zu dieser Antwort zu kommen:

1. Schreibe alle Divisoren für alle Zahlen auf:

   • Die Divisoren von 8 sind 1, 2, 4 und 8.
   • Die Divisoren von 12 sind 1, 2, 3, 4, 6 und 12.

2. Schreibe alle gemeinsamen Divisoren auf: 1, 2, 4.

3. Der größte gemeinsame Teiler ist die größte Zahl, also 4.

Der ggT von 24 und 36 ist 12. Wir können diese Antwort mit der euklidischen Methode finden:

1. Sortiere die Zahlen in aufsteigender Reihenfolge:

   24, 36.

2. Berechne den Modulo, indem du die größte Zahl als Dividend und die kleinste als Divisor nimmst:

   36 mod 24 = 12.

3. Schreibe den Divisor und den Rest in sortierter, aufsteigender Reihenfolge auf:

   12, 24.

4. Berechne die Modulo-Operation wieder auf die gleiche Weise:

   24 mod 12 = 0.

5. Es bleibt nur eine Zahl übrig (der Divisor, 12), also ist 12 der größte gemeinsame Teiler.

Der ggT von 30 und 54 ist 6. Wir können die Primfaktorzerlegung verwenden, um zu diesem Ergebnis zu kommen:

1. Schreibe alle Zahlen als Produkt ihrer Primfaktoren auf:

   • 30 = 2 ∙ 3 ∙ 5,
   • 54 = 2 ∙ 3 ∙ 3 ∙ 3.

2. Schreibe alle üblichen Primfaktoren auf: 2, 3.

3. Finde das Produkt aller gemeinsamen Primfaktoren: 2 ∙ 3 = 6.

4. Der größte gemeinsame Teiler ist das Ergebnis des vorherigen Schritts. Für 30 und 54 ist das: 6.