ggT- & kgV-Rechner

Schritt-für-Schritt-Lösung

1. 1

   Start

   Berechne gcd(252, 105) mit dem euklidischen Algorithmus: dividiere, behalte den Rest, wiederhole bis der Rest 0 ist.

   $$\gcd(252,\, 105)$$
2. 2

   Divisionsschritt 1

   Dividiere 252 durch 105 und behalte den Rest 42 — er wird der nächste Divisor.

   $$252 = 2 \cdot 105 + 42$$
3. 3

   Divisionsschritt 2

   Dividiere 105 durch 42 und behalte den Rest 21 — er wird der nächste Divisor.

   $$105 = 2 \cdot 42 + 21$$
4. 4

   Divisionsschritt 3

   21 teilt 42 genau, also stoppt der Algorithmus hier.

   $$42 = 2 \cdot 21 + 0$$
5. 5

   Der ggT ist der letzte Rest ungleich 0

   Die Reste werden kleiner, bis sie 0 erreichen; der letzte Divisor, 21, ist der ggT.

   $$\gcd(252,\, 105) = 21$$
6. 6

   Vom ggT zum kgV

   Für zwei Zahlen gilt ggT · kgV = abs(a · b). Die Division von 252 · 105 durch den ggT 21 ergibt das kgV.

   $$\operatorname{lcm}(252,\, 105) = \frac{252 \cdot 105}{\gcd(252,\, 105)} = \frac{26460}{21} = 1260$$
7. 7

   Ergebnis

   gcd(252, 105) = 21 und lcm(252, 105) = 1260