Euklidischer Algorithmus einfach erklärt.

Der euklidische Algorithmus ist ein Verfahren zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen. Er basiert auf der Eigenschaft, dass der ggT von zwei Zahlen auch der ggT der kleineren Zahl und dem Rest der Division der größeren Zahl durch die kleinere Zahl ist. Hier ist eine Schritt-für-Schritt-Erklärung: 1. **Startwerte**: Nimm zwei natürliche Zahlen \( a \) und \( b \), wobei \( a > b \). 2. **Division**: Teile \( a \) durch \( b \) und bestimme den Rest \( r \). Das bedeutet, dass du \( a = b \cdot q + r \), wobei \( q \) der ganzzahlige Quotient und \( r \) der Rest ist. 3. **Ersetzen**: Ersetze \( a \) durch \( b \) und \( b \) durch \( r \). 4. **Wiederholen**: Wiederhole die Schritte 2 und 3, bis der Rest \( r \) gleich 0 ist. 5. **Ergebnis**: Der letzte nicht-null Rest ist der größte gemeinsame Teiler der ursprünglichen Zahlen \( a \) und \( b \). **Beispiel**: Um den ggT von 48 und 18 zu finden: - \( 48 \div 18 = 2 \) (Rest 12), also \( 48 = 18 \cdot 2 + 12 \) - Ersetze: \( a = 18 \), \( b = 12 \) - \( 18 \div 12 = 1 \) (Rest 6), also \( 18 = 12 \cdot 1 + 6 \) - Ersetze: \( a = 12 \), \( b = 6 \) - \( 12 \div 6 = 2 \) (Rest 0), also \( 12 = 6 \cdot 2 + 0 \) Da der letzte nicht-null Rest 6 ist, ist der ggT von 48 und 18 gleich 6.