ggT und kgV mit dem euklidischen Algorithmus berechnen
Stand: Rechenweg mit automatischen Tests geprüftMethodik
Beim euklidischen Algorithmus teilen Sie die größere Zahl mit Rest durch die kleinere und rechnen dann mit dem Divisor und dem Rest weiter. Sobald der Rest null ist, ist der letzte Divisor der größte gemeinsame Teiler. Das kgV erhalten Sie anschließend, indem Sie das Produkt der beiden Zahlen durch diesen ggT teilen.
Zwei bis fünf ganze Zahlen ab 1, jeweils bis eine Billion.
ggT (größter gemeinsamer Teiler)
12
2^2 · 3
kgV (kleinstes gemeinsames Vielfaches)
72
2^3 · 3^2
Primfaktorzerlegung
- 24 = 2^3 · 3
- 36 = 2^2 · 3^2
Anwendung bei Brüchen
- Kürzen: 24/36 = 2/3
- Hauptnenner: 72
- Nenner 24 erweitern mit 3
- Nenner 36 erweitern mit 2
Rechenweg
- Euklidischer Algorithmus: Teile die größere durch die kleinere Zahl, rechne mit Divisor und Rest weiter, bis der Rest 0 ist. Der letzte Divisor ist der ggT.
- ggT(24, 36):
- 36 = 1 · 24 + 12
- 24 = 2 · 12 + 0
- → ggT(24, 36) = 12
- kgV(a, b) = a · b / ggT(a, b) = 24 · 36 / 12 = 72
- Kontrolle über Primfaktoren:
- 24 = 2^3 · 3
- 36 = 2^2 · 3^2
- ggT: gemeinsame Primfaktoren mit dem kleinsten Exponenten = 2^2 · 3 = 12
- kgV: alle Primfaktoren mit dem größten Exponenten = 2^3 · 3^2 = 72
- Bruch kürzen: 24/36, Zähler und Nenner durch 12 teilen = 2/3
- Hauptnenner = kgV = 72, Erweiterungsfaktoren: 24 · 3 = 72, 36 · 2 = 72
Derzeit ohne Vermittlung oder Angebotsstrecke
Diese Seite dient aktuell nur der Orientierung. rechnerportal.net vermittelt derzeit keine Anbieter und gibt keine individuelle Empfehlung ab.
Mehr Infos baldDirekt zum Tool: ggT- und kgV-Rechner öffnen
Formel
Teilen Sie die größere Zahl mit Rest durch die kleinere. Ersetzen Sie das Zahlenpaar durch Divisor und Rest und wiederholen Sie das, bis der Rest null ist. Der letzte Divisor ist der ggT, das kgV ist das Produkt geteilt durch den ggT.
a = q · b + r; ggT(a, b) = ggT(b, r); ggT(a, 0) = a; kgV(a, b) = a · b / ggT(a, b)
- a, b
- die beiden Zahlen, a ist die größere
- q
- ganzzahliger Quotient der Division
- r
- Rest der Division, immer kleiner als b
Rechenbeispiel: ggT und kgV von 24 und 36
- 1
Zahlen festlegen, die größere zuerst
= 36 und 24
- 2
Erste Division mit Rest: 36 = 1 · 24 + 12, weiter mit 24 und dem Rest 12
- 3
Zweite Division: 24 = 2 · 12 + 0, der Rest ist null, der letzte Divisor ist der ggT
= ggT = 12
- 4
kgV aus Produkt und ggT: 24 · 36 / 12
= kgV = 72
Zwei Divisionen genügen: Der ggT von 24 und 36 ist 12, das kgV ist 72. Damit lässt sich 24/36 in einem Schritt zu 2/3 kürzen, und 72 ist der kleinste gemeinsame Nenner für Brüche mit den Nennern 24 und 36.
Typische Fehler
errorIm nächsten Schritt durch den Quotienten statt durch den Rest geteilt
Nach jeder Division rückt der bisherige Divisor nach vorn und der Rest wird zum neuen Divisor. Der Quotient q wird nur notiert, für die weitere Rechnung spielt er keine Rolle. Wer mit q weiterrechnet, erhält einen falschen ggT.
errorBeim Rest null den Rest statt des Divisors als Ergebnis genommen
Der Algorithmus endet, wenn der Rest null ist. Der ggT ist dann die Zahl, durch die zuletzt geteilt wurde, also der letzte Divisor. Die Null selbst ist nie das Ergebnis, sie zeigt nur an, dass die Rechnung abgeschlossen ist.
Warum der euklidische Algorithmus den ggT findet
Der Trick des Verfahrens steckt in einer einfachen Beobachtung: Jede Zahl, die a und b teilt, teilt auch den Rest r, der bei der Division von a durch b übrig bleibt. Denn r ist nichts anderes als a minus ein Vielfaches von b. Umgekehrt teilt jeder gemeinsame Teiler von b und r auch a. Das Paar (a, b) und das Paar (b, r) haben also genau dieselben gemeinsamen Teiler und damit denselben ggT. Weil r kleiner ist als b, wird das Zahlenpaar mit jedem Schritt kleiner, bis der Rest null erreicht. Dann ist der ggT direkt ablesbar, denn jede Zahl teilt die Null.
Euklid beschrieb das Verfahren um 300 vor Christus in seinen Elementen, damals noch mit Strecken statt Zahlen: Welche größte Länge passt ohne Rest in zwei gegebene Strecken? Diese geometrische Frage ist bis heute anschaulich. Wer einen Raum mit möglichst großen quadratischen Platten ohne Zuschnitt auslegen möchte, sucht genau diesen ggT der beiden Raummaße.
Auch in der Informatik ist der Algorithmus allgegenwärtig. Er gilt als einer der ältesten noch genutzten Algorithmen überhaupt und steckt unter anderem in Verschlüsselungsverfahren, beim Rechnen mit exakten Brüchen in Programmen und in Computeralgebrasystemen. Eine erweiterte Fassung liefert zusätzlich zwei Zahlen x und y mit a · x + b · y = ggT(a, b), die man zum Beispiel braucht, um in der modularen Arithmetik zu dividieren.
Mehr als zwei Zahlen und das kgV
Bei drei oder mehr Zahlen wenden Sie den Algorithmus paarweise an: erst den ggT der ersten beiden Zahlen, dann den ggT dieses Ergebnisses mit der dritten Zahl. Für das kgV gehen Sie genauso schrittweise vor. Die Formel Produkt durch ggT gilt dabei immer nur für zwei Zahlen gleichzeitig, sonst entsteht ein zu großes Ergebnis.