Ermitteln des GGT bei großen Zahlen
Euklidischer Algorithmus
1. Initialisierung:
- Gegeben zwei Zahlen a und b, wobei a >= b
2. Division:
- Dividiere a durch b und bestimme den Rest r.
3. Iterative Schritte:
- Ersetze a durch b und b durch r.
- Wiederhole die Division, bis der Rest r gleich null ist.
4. Ergebnis:
--Wenn r = 0, dann ist der aktuelle Wert von b der größte gemeinsame Teiler
### Beispiel
Finde den GGT von 56 und 42.
1. Initialisierung:
- a = 56, b = 42
2. Erster Schritt:
- Dividiere 56 durch 42: = 42 * 1 + 14 Rest r = 14
3. Zweiter Schritt:
- Ersetze a durch 42 und b durch 14:
4. Dritter Schritt:
- Dividiere 42 durch 14: 14 * 3 + 0 Rest r = 0)
5. Ergebnis:
- Da der Rest nun 0 ist, ist der aktuelle Wert von b 14.
14 ist der GGT von 56 und 42.
### Alternative Methode: Primfaktorzerlegung
Eine andere Methode zur Ermittlung des GGT ist die Primfaktorzerlegung. Hier sind die Schritte:
1. Primfaktorzerlegung:
- Zerlege beide Zahlen in ihre Primfaktoren.
2. Gemeinsame Primfaktoren:
- Identifiziere die gemeinsamen Primfaktoren beider Zahlen.
3. Multiplikation der gemeinsamen Faktoren:
- Multipliziere die gemeinsamen Primfaktoren, um den GGT zu erhalten.
### Beispiel
Finde den GGT von 56 und 42 durch Primfaktorzerlegung.
1. Primfaktorzerlegung:
- 56: \(56 = 2^3 \cdot 7\)
- 42: \(42 = 2 \cdot 3 \cdot 7\)
2. Gemeinsame Primfaktoren:
- Die gemeinsamen Primfaktoren sind 2 und 7.
3. Multiplikation der gemeinsamen Faktoren:
- GGT: \(2^1 \cdot 7^1 = 14\)