Größter gemeinsamer Teiler

Was ist der größte gemeinsame Teiler?

Der größte gemeinsame Teiler (ggT) zweier ganzer Zahlen a und b ist die größte natürliche Zahl, die sowohl a als auch b ohne Rest teilt.

Beispiel: 12 und 18 haben die gemeinsamen Teiler 1, 2, 3 und 6 — der größte davon ist 6, also ggT(12, 18) = 6.

Der ggT wird gebraucht beim Kürzen von Brüchen, in der Kryptographie und überall dort, wo Zahlen auf eine gemeinsame Basis gebracht werden müssen.

Die Formel

Effizient berechnet wird der ggT mit dem euklidischen Algorithmus:

g = ggT(a, b)

Solange b ≠ 0:
    (a, b)  →  (b, a mod b)
Wenn b = 0:
    ggT = a

Vorzeichen werden ignoriert — der ggT ist immer positiv. ggT(0, 0) ist nicht definiert.

Die Variablen

Minimal-Beispiel

ggT(12, 18) mit dem euklidischen Algorithmus:

18 mod 12 = 6
12 mod 6  = 0   →  ggT = 6

Praxis-Beispiele

Beispiel 1 — ggT(48, 36)

48 mod 36 = 12
36 mod 12 =  0   →  ggT = 12

Beispiel 2 — ggT(252, 105)

252 mod 105 = 42
105 mod  42 = 21
 42 mod  21 =  0   →  ggT = 21

Beispiel 3 — Bruch kürzen

Der Bruch 84 / 126 soll vollständig gekürzt werden:

ggT(84, 126):
126 mod 84 = 42
 84 mod 42 =  0   →  ggT = 42

84 / 126  =  (84 / 42) / (126 / 42)  =  2 / 3

Beispiel 4 — Teilerfremde Zahlen

Wenn ggT = 1 ist, heißen zwei Zahlen teilerfremd:

35 mod 24 = 11
24 mod 11 =  2
11 mod  2 =  1
 2 mod  1 =  0   →  ggT = 1

35 und 24 sind teilerfremd.