Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler zweier Zahlen, ohne dass man ihre Teiler kennen muss. Er ist über zweitausend Jahre alt und eine Grundlage des RSA-Verfahrens.

Definition

Der größte gemeinsame Teiler zweier natürlicher Zahlen [math]\displaystyle{ a }[/math] und [math]\displaystyle{ b }[/math] ist die größte natürliche Zahl, durch die sich beide ohne Rest teilen lassen. Man schreibt [math]\displaystyle{ \operatorname{ggT}(a; b) }[/math].

Der euklidische Algorithmus ist ein Verfahren, das den größten gemeinsamen Teiler durch wiederholte Division mit Rest berechnet. Er ist nach dem griechischen Mathematiker Euklid benannt.

Teilerfremdheit

Zwei Zahlen [math]\displaystyle{ a }[/math] und [math]\displaystyle{ b }[/math] heißen teilerfremd, wenn sie außer 1 keinen gemeinsamen Teiler haben, wenn also [math]\displaystyle{ \operatorname{ggT}(a; b) = 1 }[/math] gilt. Teilerfremde Zahlen müssen selbst keine Primzahlen sein.

Beim RSA-Verfahren entscheidet die Teilerfremdheit darüber, ob ein Schlüsselpaar entsteht: Zur Zahl [math]\displaystyle{ e }[/math] des öffentlichen Schlüssels gibt es genau dann eine passende Zahl [math]\displaystyle{ d }[/math] für den privaten Schlüssel, wenn [math]\displaystyle{ e }[/math] und [math]\displaystyle{ \varphi(N) }[/math] teilerfremd sind (siehe Schlüsselerzeugung und modulares Inverses).

Verfahren

  1. Die größere Zahl wird durch die kleinere geteilt. Notiert wird die Division mit Rest: [math]\displaystyle{ a = k \cdot b + r }[/math].
  2. Danach wird der bisherige Teiler durch den Rest geteilt, wieder mit Rest.
  3. Das wiederholt sich, bis eine Division aufgeht, der Rest also 0 ist.
  4. Der letzte Rest, der nicht 0 ist, ist der größte gemeinsame Teiler. Er ist der Teiler der letzten Division.

Die untereinander geschriebenen Divisionen heißen Divisionskette.

Das Verfahren ist richtig, weil jeder gemeinsame Teiler von [math]\displaystyle{ a }[/math] und [math]\displaystyle{ b }[/math] auch den Rest [math]\displaystyle{ r = a - k \cdot b }[/math] teilt und umgekehrt jeder gemeinsame Teiler von [math]\displaystyle{ b }[/math] und [math]\displaystyle{ r }[/math] auch [math]\displaystyle{ a }[/math] teilt. Deshalb gilt

[math]\displaystyle{ \operatorname{ggT}(a; b) = \operatorname{ggT}(b; \; a \bmod b) }[/math]

Die Reste werden von Schritt zu Schritt kleiner, deshalb endet das Verfahren immer. Es endet sogar schnell: Nach je zwei Divisionen hat sich der Rest mindestens halbiert. Die Anzahl der Divisionen wächst deshalb nur mit der Stellenzahl der Zahlen. Auch bei Zahlen mit mehreren hundert Stellen sind es höchstens einige tausend Divisionen.

Bei kleinen Zahlen führt auch ein Vergleich der Teilerlisten zum Ziel: Man schreibt alle Teiler beider Zahlen auf und sucht den größten, der in beiden Listen steht. Bei großen Zahlen ist das viel zu aufwendig, weil man dafür die Zahlen in Faktoren zerlegen müsste (siehe Primfaktorzerlegung).

Umsetzung in Java

Die Schleife ersetzt das Zahlenpaar so lange durch den Teiler und den Rest, bis der Rest 0 ist (siehe while-Schleife):

public static int ggT(int a, int b) {
    while (b != 0) {
        int rest = a % b;
        a = b;
        b = rest;
    }
    return a;
}

Dieselbe Idee als Rekursion, direkt nach der Formel [math]\displaystyle{ \operatorname{ggT}(a; b) = \operatorname{ggT}(b; \; a \bmod b) }[/math]:

public static int ggTRekursiv(int a, int b) {
    if (b == 0) {
        return a;
    }
    return ggTRekursiv(b, a % b);
}

Beispiele

ggT mit der Divisionskette berechnen

Gesucht ist der größte gemeinsame Teiler von 1071 und 1029.

[math]\displaystyle{ 1071 = 1 \cdot 1029 + 42 }[/math]
[math]\displaystyle{ 1029 = 24 \cdot 42 + 21 }[/math]
[math]\displaystyle{ 42 = 2 \cdot 21 + 0 }[/math]

Die letzte Division geht auf. Der letzte Rest, der nicht 0 ist, ist 21: [math]\displaystyle{ \operatorname{ggT}(1071; 1029) = 21 }[/math].

Teilerfremdheit prüfen

Sind 179 und 69 teilerfremd?

[math]\displaystyle{ 179 = 2 \cdot 69 + 41 }[/math]
[math]\displaystyle{ 69 = 1 \cdot 41 + 28 }[/math]
[math]\displaystyle{ 41 = 1 \cdot 28 + 13 }[/math]
[math]\displaystyle{ 28 = 2 \cdot 13 + 2 }[/math]
[math]\displaystyle{ 13 = 6 \cdot 2 + 1 }[/math]
[math]\displaystyle{ 2 = 2 \cdot 1 + 0 }[/math]

Die letzte Division geht auf. Der letzte Rest, der nicht 0 ist, ist 1: [math]\displaystyle{ \operatorname{ggT}(179; 69) = 1 }[/math]. Die beiden Zahlen sind teilerfremd.

ggT über Teilerlisten bestimmen

  • Teiler von 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
  • Teiler von 96: 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96
  • gemeinsame Teiler: 1, 2, 3, 4, 6, 12

Der größte gemeinsame Teiler ist [math]\displaystyle{ \operatorname{ggT}(36; 96) = 12 }[/math]. Der euklidische Algorithmus liefert dasselbe mit weniger Aufwand:

[math]\displaystyle{ 96 = 2 \cdot 36 + 24 }[/math]
[math]\displaystyle{ 36 = 1 \cdot 24 + 12 }[/math]
[math]\displaystyle{ 24 = 2 \cdot 12 + 0 }[/math]