GGT Rechner

Berechnen Sie den größten gemeinsamen Teiler von mehreren Zahlen mit dem Euklidischen Algorithmus.

GGT berechnen

Geben Sie mindestens zwei positive ganze Zahlen ein

Beispiele ausprobieren

Praktische Anwendungen

  • Brüche kürzen: Teile Zähler und Nenner durch GGT
  • RSA-Kryptographie: Benötigt teilerfremde Zahlen
  • Chinesischer Restsatz: Gleichungssysteme lösen
  • Kalendersysteme: Periodische Ereignisse
  • Musik: Harmonische Verhältnisse
  • Codierungstheorie: Fehlerkorrektur

Erweiterte Konzepte

  • φ(n): Euler'sche Totientenfunktion
  • λ(n): Carmichael-Funktion
  • CRT: Chinesischer Restsatz
  • QR: Quadratische Reste
  • Bézout: Lineare Diophantische Gleichungen
  • Benford: Logarithmische Zahlenverteilung

💡 Wussten Sie schon?

Der Euklidische Algorithmus ist einer der ältesten bekannten Algorithmus der Menschheit und wurde bereits um 300 v. Chr. von Euklid beschrieben. Er ist extrem effizient und benötigt höchstens 5-mal so viele Schritte wie die kleinere Zahl Stellen hat. Die erweiterte Version ermöglicht RSA-Verschlüsselung und ist Basis der modernen Kryptographie!

GGT-Grundlagen

Euklidischer Algorithmus

  • Schritt 1: a ÷ b = q Rest r
  • Schritt 2: Ersetze a durch b, b durch r
  • Schritt 3: Wiederhole bis r = 0
  • Ergebnis: Letztes b ist der GGT

Wichtige Eigenschaften

  • GGT(a,0) = a
  • GGT(a,1) = 1
  • GGT(a,b) = GGT(b,a)
  • GGT(ka,kb) = k·GGT(a,b)

Tipp: Der GGT ist immer ≤ der kleineren der beiden Zahlen.

Häufig gestellte Fragen