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\)