Euklidischer Algorithmus: Größter gemeinsamer Teiler

Kurz: Ein sehr altes, schnelles Verfahren, um den größten gemeinsamen Teiler (ggT) zweier Zahlen durch wiederholte Division mit Rest zu berechnen.

Genauer: Der ggT von 48 und 18 ist 6, die größte Zahl, die beide teilt. Statt alle Teiler aufzulisten, nutzt Euklid (um 300 v. Chr.) die Beobachtung: ggT(a, b) = ggT(b, a mod b). Man ersetzt das Paar durch (b, Rest) und wiederholt, bis der Rest 0 ist. Die letzte Zahl ungleich 0 ist der ggT.

Im Detail

Beispiel

ggT(48, 18):

48 mod 18 = 12   ->  ggT(18, 12)
18 mod 12 = 6    ->  ggT(12, 6)
12 mod 6  = 0    ->  ggT = 6

Code

def ggt(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
print(ggt(48, 18))  # 6

Rekursiv: ggt(a, b) = a if b == 0 else ggt(b, a % b). Das kleinste gemeinsame Vielfache folgt daraus: kgV(a, b) = a / ggt(a, b) * b.

Wie schnell?

Die Zahl der Schritte wächst nur mit der Länge der Zahlen (logarithmisch), nicht mit ihrem Wert. Der ungünstigste Fall sind aufeinanderfolgende Fibonacci-Zahlen. Damit ist der Algorithmus auch für sehr große Zahlen praktikabel, etwa in der Kryptografie.

Erweiterung und Anwendung

Der erweiterte euklidische Algorithmus liefert zusätzlich Zahlen x und y mit a·x + b·y = ggT(a, b). Damit berechnet man das modulare Inverse, das zum Beispiel bei RSA gebraucht wird. Im Alltag kürzt man damit Brüche: Zähler und Nenner durch ihren ggT teilen.

Siehe auch: Rekursion, Big-O-Notation, Algorithmen