ggT- und kgV-Rechner
ggT und kgV von 2 bis 20 Zahlen, mit Euklid-Rechenweg und Primfaktoren.
- Sofort
- Kostenlos
- Privat (lokal verarbeitet)
- Ohne Anmeldung
ggT und kgV online berechnen, mit Rechenweg
Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) gehören zum Kern der Arithmetik: Man lernt sie in der Unterstufe beim Bruchrechnen kennen und begegnet ihnen in der Zahlentheorie wieder, beim euklidischen Algorithmus und beim Lemma von Bézout. Dieser Rechner verarbeitet 2 bis 20 ganze Zahlen und zeigt den Weg zum Ergebnis: Divisionen mit Rest, Primfaktorzerlegung, Bézout-Koeffizienten und den gekürzten Bruch.
Wer ggT und kgV sicher bestimmt, kürzt Brüche schneller, findet den Hauptnenner, löst Aufgaben vom Typ „Wann treffen sie sich wieder?“ und teilt Flächen in gleich große Quadrate. Schülerinnen und Schüler, Eltern bei den Hausaufgaben, Lehrkräfte beim Erstellen von Lösungen und Entwickler, die mit Zyklen, Zahnrädern oder RSA-Schlüsseln arbeiten, erhalten ein exaktes Ergebnis samt vollständigem Rechenweg.
-
Zahlen eingeben
Tippen Sie in das Feld „Ganze Zahlen (2 bis 20)“ 2 bis 20 Zahlen, getrennt durch Kommas, Leerzeichen oder Semikolons, oder klicken Sie auf ein Beispiel.
-
ggT und kgV ablesen
Die beiden Karten aktualisieren sich beim Tippen; die Schaltfläche „Kopieren“ legt die Zahl ohne Trennzeichen in die Zwischenablage.
-
Eigenschaften prüfen
Darunter steht, ob die Zahlen teilerfremd sind (ab drei Zahlen auch, ob paarweise), und bei zwei Zahlen die Probe ggT × kgV = a × b, das Lemma von Bézout und der gekürzte Bruch a/b.
-
Erklärungen aufklappen
„Euklidischer Algorithmus, Schritt für Schritt“ zeigt jede Division a = q × b + r; „Primfaktorzerlegung“ zeigt die kleinsten und größten Exponenten.
So berechnet man ggT und kgV: Euklid und Primfaktoren
Das Tool verwendet den euklidischen Algorithmus: Die größere Zahl wird mit Rest durch die kleinere geteilt, a = q × b + r, dann geht es mit b und dem Rest r weiter, denn ggT(a, b) = ggT(b, r). Der letzte Rest ungleich 0 ist der ggT. Das kgV folgt ohne Zerlegung: kgV(a, b) = a × b ÷ ggT(a, b).
Bei mehr als zwei Zahlen wird verkettet: ggT(a, b, c) = ggT(ggT(a, b), c), ebenso beim kgV. Das Primfaktor-Feld zeigt die zweite Schulmethode: Mit a = 2α × 3β × … nimmt der ggT jeden gemeinsamen Primfaktor mit dem kleinsten Exponenten, das kgV jeden vorkommenden Primfaktor mit dem größten Exponenten.
aundb: Dividend und Divisor jeder Zeile (die größere Zahl zuerst).q: der ganzzahlige Quotient;r: der Rest, stets zwischen 0 und b − 1.ggT: die größte ganze Zahl, die alle Zahlen teilt;kgV: die kleinste positive Zahl, die durch alle teilbar ist.uundv: die Bézout-Koeffizienten, ganze Zahlen (auch negativ) mitu × a + v × b = ggT(a, b), aus dem erweiterten euklidischen Algorithmus.α,β…: die Exponenten der Zerlegung, z. B. 12 = 22 × 31.
Beispiele: ggT und kgV berechnen
| Eingabe | ggT | kgV | Was das Tool außerdem zeigt |
|---|---|---|---|
12, 18 | 6 | 36 | 6 × 36 = 216 = 12 × 18; Bézout: (−1) × 12 + 1 × 18 = 6; 12/18 = 2/3 |
8, 12, 20 | 4 | 120 | ggT(8, 12) = 4, dann ggT(4, 20) = 4; kgV: 24, dann 120 |
17, 31 | 1 | 527 | Teilerfremd; 11 × 17 + (−6) × 31 = 1 |
1071, 462 | 21 | 23.562 | 3 Divisionen; (−3) × 1.071 + 7 × 462 = 21; 1.071/462 = 51/22 |
6, 10, 15 | 1 | 30 | Insgesamt teilerfremd, aber nicht paarweise (6 und 10 haben den Faktor 2) |
2, 3, 5, 7, 11, 13, 17, 19, 23 | 1 | 223.092.870 | Paarweise teilerfremd: Das kgV ist das Produkt |
Wofür braucht man ggT und kgV?
- Brüche: 12/18 mit dem ggT 6 zu 2/3 kürzen oder 5/12 + 7/18 auf den Hauptnenner 36 = kgV(12, 18) bringen: 15/36 + 14/36 = 29/36.
- Takte und Fahrpläne: Zwei Busse fahren um 8:00 Uhr gemeinsam ab, einer alle 12, der andere alle 18 Minuten; gemeinsam fahren sie erst wieder um 8:36 Uhr, nach kgV = 36 Minuten.
- Zuschnitt und Fliesen: Eine Platte von 120 cm × 84 cm lässt sich ohne Verschnitt mit möglichst großen Quadraten von ggT(120, 84) = 12 cm belegen, also mit 10 × 7 = 70 Stück.
- Zahnräder und Rhythmen: Räder mit 12 und 18 Zähnen stehen wieder in der Ausgangsstellung, wenn 36 Zähne ineinandergegriffen haben, also nach 3 Umdrehungen des kleinen und 2 des großen Rads.
- Kryptografie: Bei RSA muss der öffentliche Exponent e zu φ(n) teilerfremd sein, und der private Schlüssel d ist sein Inverses modulo φ(n), das man mit Bézout bestimmt. Für e = 17 und φ(n) = 3.120 zeigt das Tool (−367) × 17 + 2 × 3.120 = 1, also d = −367 + 3.120 = 2.753; tatsächlich ist 17 × 2.753 = 15 × 3.120 + 1.
Typische Fehler
- ggT und kgV verwechseln: Der ggT ist nie größer als die kleinste Zahl, das kgV nie kleiner als die größte. Ein „ggT“ von 36 für 12 und 18 ist also sicher falsch.
- Zahlen einfach multiplizieren: 12 × 18 = 216, das kgV ist aber 36. Das Produkt zweier Zahlen ist nur dann ihr kgV, wenn sie teilerfremd sind (17 × 31 = 527).
- ggT × kgV = Produkt auf drei Zahlen anwenden: Für 8, 12 und 20 ist 4 × 120 = 480, aber 8 × 12 × 20 = 1.920.
- Tausenderpunkte oder Dezimalkommas eingeben: Das Komma trennt die Liste, „12,5“ wird also als 12 und 5 gelesen, und „1.071“ gilt als Dezimalzahl. Schreiben Sie 1071 ohne Trennzeichen.
Alle Berechnungen laufen lokal in Ihrem Browser mit exakter Ganzzahl-Arithmetik (BigInt): Keine Zahl wird an einen Server gesendet. Grenzen: 2 bis 20 ganze Zahlen ungleich 0 mit höchstens 15 Ziffern; die Primfaktorzerlegung erscheint nur, wenn jeder Primfaktor schnell gefunden wird (Probedivision bis 1.000.000, danach ein Primzahltest).
Häufige Fragen
Was ist der Unterschied zwischen ggT und kgV?
Der ggT (größter gemeinsamer Teiler) ist die größte Zahl, die alle Ihre Zahlen teilt; das kgV (kleinstes gemeinsames Vielfaches) ist die kleinste positive Zahl, die durch alle teilbar ist. Für 12 und 18 sind die gemeinsamen Teiler 1, 2, 3 und 6, also ist der ggT 6; die gemeinsamen Vielfachen sind 36, 72, 108 …, also ist das kgV 36. Mit dem ggT kürzt man, mit dem kgV findet man den Hauptnenner.
Wie funktioniert der euklidische Algorithmus?
Man teilt die größere Zahl mit Rest durch die kleinere und rechnet dann mit dem Divisor und dem Rest weiter, bis der Rest 0 ist. Für 1.071 und 462: 1.071 = 2 × 462 + 147, dann 462 = 3 × 147 + 21, dann 147 = 7 × 21 + 0. Der letzte Rest ungleich 0, also 21, ist der ggT, gefunden in nur 3 Divisionen.
Warum gilt ggT × kgV = a × b?
Bei zwei Zahlen kommt jeder Primfaktor einmal mit dem kleineren Exponenten (im ggT) und einmal mit dem größeren (im kgV) vor, zusammen also genau a × b. Für 12 und 18: 6 × 36 = 216 = 12 × 18. Auf drei oder mehr Zahlen lässt sich die Regel nicht übertragen: Für 8, 12 und 20 ist 4 × 120 = 480, aber 8 × 12 × 20 = 1.920.
Was bedeutet teilerfremd?
Zwei Zahlen sind teilerfremd, wenn ihr ggT 1 ist, etwa 17 und 31; ihr kgV ist dann einfach ihr Produkt 527. Bei drei oder mehr Zahlen unterscheidet das Tool „insgesamt teilerfremd“ und „paarweise teilerfremd“: 6, 10 und 15 haben den ggT 1, aber 6 und 10 haben den gemeinsamen Faktor 2, deshalb ist das kgV 30 und nicht das Produkt 900.
Wozu dient das Lemma von Bézout?
Es besagt, dass es ganze Zahlen u und v mit u × a + v × b = ggT(a, b) gibt; das Tool bestimmt sie mit dem erweiterten euklidischen Algorithmus, etwa (−1) × 12 + 1 × 18 = 6. Damit löst man lineare diophantische Gleichungen ax + by = c und berechnet modulare Inverse: 11 × 17 + (−6) × 31 = 1 zeigt, dass 11 das Inverse von 17 modulo 31 ist. Genau so wird bei RSA der private Schlüssel berechnet.
Wie berechnet man ggT und kgV von drei Zahlen?
Man rechnet schrittweise mit je zwei Zahlen: ggT(8, 12, 20) = ggT(ggT(8, 12), 20) = ggT(4, 20) = 4 und kgV(8, 12, 20) = kgV(kgV(8, 12), 20) = kgV(24, 20) = 120. Mit Primfaktoren folgt aus 8 = 2³, 12 = 2² × 3 und 20 = 2² × 5, dass ggT = 2² = 4 und kgV = 2³ × 3 × 5 = 120. Das Tool akzeptiert bis zu 20 ganze Zahlen ungleich 0 mit höchstens 15 Ziffern, rechnet mit BigInt ohne Rundung und ignoriert Minuszeichen.