Rechner · Klasse 5 bis Studium
ggT und kgV berechnen: Rechner mit Rechenweg
Der Rechner bestimmt den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache von beliebig vielen Zahlen. Er zeigt die Primfaktorzerlegung, den euklidischen Algorithmus als Tabelle und auf Wunsch die Darstellung des ggT als Summe.
So benutzt du den Rechner
Gib zwei oder mehr ganze Zahlen ein, getrennt durch Komma, Semikolon oder Leerzeichen. Der Rechner bestimmt ggT und kgV aller Zahlen gemeinsam und erklärt den Weg über die Primfaktorzerlegung. Für die ersten beiden Zahlen zeigt er außerdem den euklidischen Algorithmus, der auch bei sehr großen Zahlen blitzschnell funktioniert.
ggT und kgV mit Primfaktoren
Zerlege alle Zahlen in Primfaktoren und schreibe sie mit Hochzahlen. Dann gilt:
- ggT: Nimm nur die Primfaktoren, die in allen Zahlen vorkommen, jeweils mit der kleinsten Hochzahl.
- kgV: Nimm alle Primfaktoren, die irgendwo vorkommen, jeweils mit der größten Hochzahl.
Der euklidische Algorithmus
Schon Euklid beschrieb um 300 v. Chr. ein Verfahren, das ganz ohne Primfaktoren auskommt. Man teilt die größere Zahl mit Rest durch die kleinere, dann die kleinere durch den Rest, und so weiter, bis der Rest 0 ist. Der letzte Teiler ist der ggT.
| Rechnung | Rest |
|---|---|
| 126 = 1 · 84 + 42 | 42 |
| 84 = 2 · 42 + 0 | 0, also ggT = 42 |
Das Verfahren ist eines der ältesten Algorithmen der Welt und wird bis heute in Computern eingesetzt, etwa in der Verschlüsselung. Das kgV zweier Zahlen bekommst du danach mit der Formel kgV(a, b) = a · b : ggT(a, b), hier 84 · 126 : 42 = 252.
Erweitert: ggT als Summe (Lemma von Bézout)
Der erweiterte euklidische Algorithmus findet zusätzlich ganze Zahlen s und t, sodass ggT(a, b) = s · a + t · b gilt. Für 84 und 126 ist 42 = (−1) · 84 + 1 · 126. Diese Darstellung braucht man in der Zahlentheorie, zum Beispiel beim Lösen von Gleichungen in ganzen Zahlen oder beim Berechnen von Schlüsseln im RSA-Verfahren.
Wozu braucht man ggT und kgV?
Den ggT brauchst du zum Kürzen: 84/126 wird mit dem ggT 42 zu 2/3. Das kgV ist der Hauptnenner beim Addieren von Brüchen: Für 1/84 + 1/126 ist 252 der kleinste gemeinsame Nenner. Beides erledigt auch der Bruchrechner. Im Alltag beantwortet das kgV Fragen wie: Zwei Busse fahren alle 12 und alle 18 Minuten ab. Wann fahren sie wieder gleichzeitig? Nach kgV(12, 18) = 36 Minuten.
Häufige Fragen
Was ist der ggT von zwei Primzahlen?
Immer 1, denn Primzahlen haben außer 1 und sich selbst keine Teiler. Zahlen mit dem ggT 1 heißen teilerfremd. Ihr kgV ist einfach ihr Produkt.
Gilt ggT · kgV = a · b auch für drei Zahlen?
Nein, nur für zwei. Für 2, 4 und 8 ist ggT = 2 und kgV = 8, das Produkt der Zahlen ist aber 64 und nicht 16.
Wie groß dürfen die Zahlen sein?
Der euklidische Algorithmus funktioniert mit beliebig großen ganzen Zahlen. Die Primfaktorzerlegung wird nur angezeigt, solange sie sich in kurzer Zeit berechnen lässt. Bei Zahlen mit sehr großen Primfaktoren erscheint deshalb nur der Weg mit Euklid.
Weiterlesen
Klasse 5–8