GCD
Der ggT (größter gemeinsamer Teiler) ist die größte positive ganze Zahl, die zwei oder mehr ganze Zahlen teilt, effizient berechnet mit dem euklidischen Algorithmus.
Zweck
Den größten gemeinsamen Teiler von ganzen Zahlen finden, verwendet in der Bruchreduktion und Zahlentheorie.
Mechanismus
Euklidischer Algorithmus: gcd(a,b) = gcd(b, a mod b), bis b=0. Der erweiterte euklidische Algorithmus bestimmt zusätzlich Bézout-Koeffizienten x,y mit ax+by=gcd(a,b), verwendet für modulare Inverse. lcm(a,b) = |a×b|/gcd(a,b).
Anwendungsfälle
- Bruchreduktion
- Berechnung modularer Inverser
- RSA-Schlüsselvalidierung
- Rationale Arithmetik
Beispiele
- Eingabe
gcd(48, 18)Output648=6×8, 18=6×3
Häufige Fehler
- gcd with 0 left unhandled
- gcd(a,0)=|a|, gcd(0,0)=0
Verwandte Begriffe
LCM
Das kgV (kleinstes gemeinsames Vielfaches) ist die kleinste positive ganze Zahl, die ein Vielfaches von zwei oder mehr ganzen Zahlen ist, berechnet über den ggT. GLOSSAR
Modular Arithmetic
Modulare Arithmetik nimmt Reste nach Ganzzahloperationen und hält Ergebnisse in [0, n); sie ist die Grundlage der Zahlentheorie und Kryptographie. GLOSSAR
Prime Number
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist; sie ist der Baustein der Zahlentheorie, und jede ganze Zahl zerfällt eindeutig in Primfaktoren. GLOSSAR