Teilbarkeit, ggT, kgV

Definition · Teilt

a | b heißt: es gibt ein k mit b = a · k.

3 | 12, weil 12 = 3 · 4

Tausende Jahre alt, immer noch der schnellste Weg:

ggT(a, b) berechnen:
  Wenn b = 0  →  Antwort: a
  Sonst       →  ggT(b, a mod b)

ggT(48, 36)
= ggT(36, 48 mod 36) = ggT(36, 12)
= ggT(12, 36 mod 12) = ggT(12, 0)
= 12

⚡

GeschwindigkeitEuklid braucht O(log n) Schritte — auch bei 100-stelligen Zahlen ist er in Sekunden fertig. Probiere das mit Brute-Force!

kgV(a, b) = (a · b) / ggT(a, b)

Beispiel: kgV(12, 18) = (12 · 18) / ggT(12, 18) = 216 / 6 = 36