ggT, kgV & Primzahlen

Größter gemeinsamer Teiler, kleinstes gemeinsames Vielfaches, Primfaktoren und Teiler

Was möchtest du berechnen?

ggT & kgVPrimfaktoren & Teiler

Ergebnis

ggT: 12; größter gemeinsamer Teiler

kgV: 2.520; kleinstes gemeinsames Vielfaches

Rechenweg

Rechenweg anzeigen

ggT(84, 36) mit dem euklidischen Algorithmus:

84 = 2 · 36 + 12
36 = 3 · 12 + 0
→ ggT(84, 36) = 12

ggT(12, 120) mit dem euklidischen Algorithmus:
```
120 = 10 · 12 + 0
→ ggT(12, 120) = 12
```
kgV über den ggT: kgV(a, b) = a · b ÷ ggT(a, b).
```
kgV(84, 36) = 84 · 36 ÷ 12 = 252
```
Mit der nächsten Zahl weiter: kgV(252, 120).
```
kgV(252, 120) = 252 · 120 ÷ 12 = 2.520
```

Ergebnis für alle Zahlen:

ggT(84, 36, 120) = 12
kgV(84, 36, 120) = 2.520

Probe über die Primfaktoren: Für den ggT jeden gemeinsamen Primfaktor mit der kleinsten Hochzahl nehmen, für das kgV jeden Primfaktor mit der größten.
```
84 = 2² · 3 · 7
36 = 2² · 3²
120 = 2³ · 3 · 5
ggT = 2² · 3
kgV = 2³ · 3² · 5 · 7
```

So wird gerechnet

ggT mit dem euklidischen Algorithmus: a = q · b + r, dann mit b und r weiter, bis der Rest 0 ist; der letzte Teiler ist der ggT. Bei mehr als zwei Zahlen gilt ggT(a, b, c) = ggT(ggT(a, b), c). kgV über den ggT: kgV(a, b) = a · b ÷ ggT(a, b).

Primfaktorzerlegung: Die Zahl wird fortlaufend durch Primzahlen geteilt. Kleine Faktoren findet die Probedivision, große der Pollard-Rho-Algorithmus; ob ein Rest prim ist, entscheidet der Miller-Rabin-Test, der mit festen Basen für alle Zahlen dieser Größe sicher ist. So bleibt die Rechnung auch bei 18-stelligen Zahlen schnell.

Teiler: Bei n = p₁^e₁ · p₂^e₂ · … gibt es (e₁ + 1) · (e₂ + 1) · … Teiler. 360 = 2³ · 3² · 5 hat 4 · 3 · 2 = 24 Teiler.