Wie berechnet man den größten gemeinsamen Teiler (ggT)?

Bestimme den ggT von $54$ und $64$.

Im ersten Schritt schauen wir, durch welche Zahlen die Zahl $54$ teilbar ist. Dies geschieht der Reihe nach:

$2 \; \rightarrow$ ja; $3 \; \rightarrow$ ja; $4 \; \rightarrow$ nein; und so weiter. So entsteht eine Liste mit allen Zahlen, durch die die Zahl $54$ teilbar ist:

$2,\;3,\;6,\;9,\;18,\;27,\;54$

Dasselbe Verfahren verwenden wir, um zu schauen, durch welche Zahlen die zweite Zahl $64$ teilbar ist:

$2,\;4,\;8,\;16,\;32,\;64$

Jetzt vergleichen wir die beiden Listen miteinander und suchen den größten Wert, der in beiden Listen vorkommt. Dies ist der größte gemeinsame Teiler. Hier ist es die Zahl $2$.

Bestimme den ggT von $60$ und $70$.

Im ersten Schritt zerlegen wir die Zahl $60$ in ihre Primfaktoren. Diese werden der Größe nach sortiert:

$2 \cdot 2\cdot 3\cdot 5$

Die Primfaktoren der zweiten Zahl errechnen wir im nächsten Schritt:

$2\cdot 5\cdot 7$

Im nächsten Schritt vergleichen wir die beiden Primzahlenlisten und stellen fest, dass in beiden Listen einmal die Zahl $2$ und einmal die Zahl $5$ vorkommt. Die Multiplikation der beiden Zahlen, also $2\cdot5$, ergibt $10$. Somit ist der größte gemeinsame Teiler die Zahl $10$.

Wenn Faktoren in beiden Primfaktorzerlegungen mehrfach auftreten werden diese auch mehrfach in der Rechnung multipliziert.