Teilbarkeit und PrimzahlenGcd

Auch hier können wir mit der Primfaktorzerlegung den ggT von zwei beliebigen Zahlen berechnen. Bedenke, dass jeder Teiler einer Zahl einige der Primfaktoren dieser Zahl beinhalten muss.

Angenommen, X ist der ggT von 18 und 30, dann lässt sich 18 durch X teilen, weshalb die Primfaktoren von X auch 2, 3 und 3 beinhalten müssen. Außerdem lässt sich 30 auch durch X teilen, weshalb die Primfaktoren von X ebenso 2, 3 und 5 beinhalten müssen.