Bestimmen des ggT durch Auflisten aller Teiler

Die folgende Methode zum Bestimmen des größten gemeinsamen Teilers (ggT) ist einfach zu verstehen:

Wir zählen alle Teiler der Zahlen auf, deren ggT wir bestimmen sollen, und lesen dann den ggT ab.

Dies ist übersichtlich, wird jedoch bei größeren Zahlen aufwändig.

Beispiel: Bestimme den ggT der Zahlen 8 und 12, indem du alle Teiler aufschreibst.

Um die Teiler von 8 zu bestimmen, schaut man sich zunächst an, durch welche Zahlen die Zahl 8 teilbar ist, sodass man als Ergebnis eine natürliche Zahl erhält (Kommazahlen sind nicht erlaubt).

8:1 = 8
8:2 = 4
8:3
8:4 = 2
8:5
8:6
8:7
8:8 = 1

Man erkennt nun die Teiler von 8, diese sind: 1, 2, 4, 8

Bestimmt man mit dem selben Verfahren die Teiler von 12 erhält man: 1, 2, 3, 4, 6, 12

Jetzt schaut man sich den größten dieser Teiler an, der in beiden Listen auftaucht (den also beide gemeinsam haben). In diesem Fall wäre das die Zahl 4. Die 4 ist also ggT von 8 und 12.

Mathematisch schreibt man dies: ggT(8, 12) = 4

Problematisch wird dieses Verfahren bei größeren Zahlen, die viele Teiler besitzen. Dann nutzen wir das Bestimmen des ggT durch Primfaktorzerlegung.