Der euklidische Algorithmus

Gemeinsame Teiler und der euklidische Algorithmus · Abschnitt 18 von 64

Satz

Der Rest verändert den ggT nicht

Gilt $a=bq+r$ , dann teilen $a$ und $b$ dieselben gemeinsamen Teiler wie $b$ und $r$ . Deshalb gilt $\operatorname{ggT}(a,b)=\operatorname{ggT}(b,r)$ .

Beweis

Warum?

Ein gemeinsamer Teiler von $a$ und $b$ teilt auch $r=a-bq$ . Umgekehrt teilt ein gemeinsamer Teiler von $b$ und $r$ auch $a=bq+r$ . Die gemeinsamen Teiler stimmen also überein.

Gelöstes Beispiel

Beispiel: 252 und 105

$252=2\cdot105+42$ , $105=2\cdot42+21$ , $42=2\cdot21+0$ . Der letzte von 0 verschiedene Rest ist 21, also $\operatorname{ggT}(252,105)=21$ .

Checkliste

Algorithmus sicher ausführen

Größere durch kleinere Zahl mit Rest teilen.
Das Paar durch kleinere Zahl und Rest ersetzen.
Bis zum Rest 0 wiederholen.
Den letzten von 0 verschiedenen Rest nennen.