Größter gemeinsamer Teiler

Der größte gemeinsame Teiler wird mit ggT abgekürzt. Der ggT ist wichtig für die Bruchrechnung zum Kürzen eines Bruchs. Der ggT wird von zwei natürlichen Zahlen brechnent. Es handelt sich um die größte Zahl, durch die man die beiden Zahlen teilen kann.

Schauen wir uns ein Besipiel an. Die beiden Zahlen seien 12 und 20. Teiler von 12 sind 6, 4, 3 und 2. Teiler von 20 sind 10, 5, 4 und 2. Der größte gemeinsame Teiler ist folglich die 4.

Man kann sich vorstellen, daß für größere Zahlen der ggT nicht so einfach zu finden ist. Deshalb wollen wir eine Algorithmus lernen, der uns sicher zum Ziel führt.

Die beiden Zahlen werden in ihre Primfaktoren zerlegt. Zur Darstellung der Primfaktoren benutzen wir die Potenzschreibweise. Wenn ein Primfaktor in beiden Zahlen vorkommt, wählen wir die kleinste Potenz von diesem Primfaktor aus. Das Produkt aller ausgewählten Primfaktoren ist der ggT.

Wenn beide Zahlen teilerfremd sind, also keinen gemeinsamen Teiler haben, so gibt es keinen Primfaktor, den wir auswählen können. In diesem Fall ist der ggT 1.

Schauen wir uns das für unser Beispiel an: