Größter gemeinsamer Teiler & kleinstes gemeinsames Vielfaches
Berechne ggT und kgV zweier ganzer Zahlen mit dem Euklidischen Algorithmus – Grundlage für Bruchrechnung und Zahlentheorie.
Erklärung
Der größte gemeinsame Teiler (ggT) zweier Zahlen ist die größte natürliche Zahl, die beide ohne Rest teilt. Das kleinste gemeinsame Vielfache (kgV) ist die kleinste natürliche Zahl, die ein Vielfaches von beiden ist. Beide hängen über die Beziehung ggT(a,b) · kgV(a,b) = a · b zusammen. Der Euklidische Algorithmus berechnet den ggT effizient: Teile a durch b mit Rest r. Ersetze a durch b und b durch r. Wiederhole, bis r = 0. Der letzte nicht-Null-Wert ist der ggT. Beispiel ggT(48, 36): 48 = 1·36 + 12, 36 = 3·12 + 0. Also ggT = 12. Daraus folgt das kgV: kgV(48, 36) = 48·36/12 = 144. Anwendungen: In der Bruchrechnung kürzt man Brüche durch den ggT von Zähler und Nenner (24/36 = 2/3, weil ggT = 12). Beim Addieren ungleichnamiger Brüche bringt man sie auf den Hauptnenner – das kgV der Nenner. Auch im Alltag praktisch: Zwei Bahnen fahren alle 12 bzw. 18 Minuten – wann kommen sie wieder gleichzeitig? kgV(12, 18) = 36 Minuten. In der Zahlentheorie ist der Euklidische Algorithmus über 2300 Jahre alt und immer noch der schnellste Weg. Er bildet die Grundlage für moderne Kryptografie (RSA-Verschlüsselung), für Modulararithmetik und das Lemma von Bezout: Es gibt immer ganze Zahlen x, y mit a·x + b·y = ggT(a, b).
Häufige Fragen
Wie funktioniert der Euklidische Algorithmus? +
Wiederhole: Ersetze (a, b) durch (b, a mod b). Sobald b = 0, ist a der ggT. Beispiel: ggT(48, 36) → (36, 12) → (12, 0). ggT = 12.
Was ist der Unterschied zwischen ggT und kgV? +
ggT ist der größte gemeinsame Teiler (kleines Ergebnis), kgV das kleinste gemeinsame Vielfache (großes Ergebnis). Sie ergänzen sich: ggT · kgV = a · b.
Wofür braucht man den ggT? +
Brüche kürzen, Zahnräder dimensionieren, Zyklen synchronisieren, Faktorisieren großer Zahlen, Kryptografie.
Wofür braucht man das kgV? +
Brüche addieren (Hauptnenner), Periodendauern bestimmen, gemeinsame Termine berechnen.
Was ist mit ggT(0, 0)? +
Konvention: ggT(0, 0) = 0. Sonst gilt: ggT(a, 0) = a, weil 0 jedes Vielfache jeder Zahl ist.