Zur Themenübersicht    

Problem

Wie erhält man den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen a und b?

Lösung

Wie nehmen an: a ist größer als b.

Wenn a ein Vielfaches von b ist (oder eben b Teiler von a) dann ist natürlich b der ggT dieser beiden Zahlen.

Ist b nicht Teiler von a, dann kann man sich folgendermaßen helfen:  Man teilt die Zahl a durch b. Das Ergebnis besteht aus einer natürlichen Zahl und einem für uns wichtigen Rest (ebenfalls eine natürliche Zahl).  Der ggt aus der kleineren Zahlen b und dem Rest ist dann auch der ggT von a und b. Der ggT von b und dem Rest kann dann nach dem gleichen Prinzip berechnet werden. Das heißt:  Im nächsten Schritt wird a der vorherige Wert von b, und b der vorherige Wert vom Rest zugewiesen.
Dieses Teilen und Werte zuweisen geschieht so lange, bis der Rest Null ergibt. Ist dies erreicht, dann ist der b-Wert aus diesem Schritt der gesuchte ggT.

Beispiel

Zur Themenübersicht
Zum Seitenanfang

Zur nächsten Seite