Das kleinste gemeinsame Vielfache und der größte gemeinsame Teiler zweier Zahlen sind zwei wichtige und nützliche Objekte in der Arithmetik. Ihre Definitionen stecken im Grunde bereits in ihren Namen: Der größte gemeinsame Teiler (\(\textrm{ggT}\)) zweier natürlicher Zahlen ist definiert als die größte Zahl, die sowohl die eine, als auch die andere Zahl teilt; das kleinste gemeinsame Vielfache(\(\textrm{kgV}\)) zweier natürlicher Zahlen ist dementsprechend die kleinste Zahl, die sowohl ein Vielfaches der einen, als auch ein Vielfaches der anderen ist.

Beispielsweise ist 6 der \(\textrm{ggT}\) von \(24\) und \(30\), während \(120\) das \(\textrm{kgV}\) dieser Zahlen ist. Der \(\textrm{ggT}\) von \(5\) und \(100\) ist \(5\), ihr \(\textrm{kgV}\) ist \(100\). Zahlen, deren \(\textrm{ggT} 1\) ist, heißen teilerfremd. Zwei verschiedene Primzahlen sind stets teilerfremd, aber auch z.B. \(15\) und \(28\) sind teilerfremde Zahlen. Es gibt einen wichtigen Zusammenhang zwischen dem \(\textrm{kgV}\) und dem \(\textrm{ggT}\): das Produkt von \(\textrm{ggT}\) und dem \(\textrm{kgV}\) zweier Zahlen ist immer gleich dem Produkt der Zahlen selber; im obigen Beispiel hatten wir \(6\) bzw. \(120\) als \(\textrm{ggT}\) bzw. \(\textrm{kgV}\) der Zahlen \(24\) und \(30\) und tatsächlich ist \(6 \cdot 120 = 720 =24 \cdot 30\).

Es gibt verschiedene Wege, den \(\textrm{ggT}\) und das \(\textrm{kgV}\) zweier Zahlen zu berechnen, von denen hier drei vorgestellt werden sollen:

Teiler- bzw. Vielfachenvergleich

Diese Methode ist die am einfachsten zu verstehende, aber gleichzeitig auch (für große Zahlen) diejenige mit dem höchsten Rechenaufwand. Für den \(\textrm{ggT}\) erstellt man einfach für beide Zahlen eine Liste der Teiler. Anschließend vergleicht man diese Listen und sucht nach der größten Zahl, die in beiden Listen auftaucht. Für \(24\) sind die Teiler \(1\), \(2\), \(3\), \(4\), \(6\), \(8\), \(12\), \(24\). Für \(30\) hat man die Teiler \(1\), \(2\), \(3\), \(5\), \(6\), \(10\), \(15\), \(30\). Da \(6\) die größte Zahl ist, die in beiden Listen auftaucht, ist \(6\) der \(\textrm{ggT}\) von \(24\) und \(30\). Bei dem \(\textrm{kgV}\) geht man analog vor: Zu beiden Zahlen erstellt man eine Liste mit Vielfachen (da die Liste eigentlich unendlich lang wäre, hört man bei dem Produkt der beiden Zahlen auf – größer kann das \(\textrm{kgV}\) ja nicht sein), und vergleicht die Listen anschließend. Die kleinste Zahl, die in beiden Listen auftaucht ist dann das \(\textrm{kgV}\) dieser Zahlen.
Die Vielfachen von \(24\) sind:

\(24\), \( 48\), \( 72\), \( 96\), \( 120\), \( 144\), \( 168\), \( 192\), \( 216\), \( 240\), \( 264\), \( 288\), \( 312\), \( 336\), \( 360\), \( 384\), \( 408\), \( 432\), \( 456\), \( 480\), \( 504\), \( 528\), \( 552\), \( 576\), \( 600\), \( 624\), \( 648\), \( 672\), \( 696\), \( 720\),...

Die Vielfachen von \(30\) sind:

\(30\), \(60\), \(90\), \(120\), \(150\), \(180\), \(210\), \(240\), \(270\), \(300\), \(330\), \( 360\), \( 390\), \( 420\), \( 450\), \( 480\), \( 510\), \( 540\), \( 570\), \( 600\), \( 630 \), \(660\), \( 690\), \( 720\),...

Die kleinste Zahl, die auf beiden Listen steht, ist \(120\), das heißt das \(\textrm{kgV}\) von \(30\) und \(24\) ist \(120\).

eine weitere Methode zu bestimmung von \(\textrm{ggT}\) und \(\textrm{kgV}\) ist der

Vergleich der Primfaktorzerlegungen:

Bei dieser Methode werden die Primfaktorzerlegungen der beiden Zahlen verglichen: man schreibt zunächst die Primfaktorzerlegungen der beiden Zahlen übereinander. Anschließend sucht man für den \(\textrm{ggT}\) nach denjenigen Primzahlen, die in beiden Zerlegungen vorkommen. Danach betrachtet für jede dieser Primzahlen den jeweils kleineren Exponenten. Das Produkt dieser Primzahlen hoch den jeweils kleineren Exponenten ist dann der \(\textrm{ggT}\) dieser Zahlen. Beispiel:
\(24= 2^3 \cdot 3^1 30=2^1 \cdot 3^1 \cdot 5^1\)
die gemeinsame Primfaktoren sind: \(2\) (kleinster Exponent \(1\)), \(3\) (kleinste Exponent \(1\)). Das heißt, \begin{align*}\textrm{ggT}(24,30)=2^1 \cdot 3^1=6.\end{align*}
Für das \(\textrm{kgV}\) betrachtet man zunächst alle auftretenden Primfaktoren und bei diesen Primfaktoren jeweils den größten Exponenten. Das Produkt dieser Primzahlen hoch den jeweils größeren Exponenten ist dann das \(\textrm{kgV}\). Beispiel:
\(24=2^3 \cdot 3^1 30=2^1 \cdot 3^1 \cdot 5^1\)
alle vorkommenden Primfaktoren sind: \(2\) (größter Exponent \(3\)), \(3\) (größter Exponent \(1\)), \(5\) (größter Exponent \(1\)). Das heißt, \begin{align*}\textrm{kgV}(24,30)=2^3 \cdot 3^1 \cdot 5^1=8 \cdot 3 \cdot 5=120.\end{align*}
Wie du im Kapitel Primzahlen erfahren hast, ist die Primfaktorzerlegung für große Zahlen nicht immer einfach. Für die Bestimmung des \(\textrm{ggT}\) benutzt man daher häufig effizientere Verfahren, der bekannteste ist der sog. Euklidische Algorithmus

Euklidischen Algorithmus

Der Euklidische Algorithmus ist eine äußerst effiziente Methode für die Bestimmung des \(\textrm{ggT}\). Man setzt ihn ein, wenn man den \(\textrm{ggT}\) von besonders großen Zahlen berechnen will. Erstaunlicherweise ist er bereits über 2000 Jahre alt!
Man dividiert zunächst die kleinere durch die größere Zahl (mit Rest). Anschließend teilt man den Rest durch die kleinere Zahl und erhält einen neuen Rest. So geht man weiter vor, bis irgendwann der Rest Null ist. Der \(\textrm{ggT}\) der beiden Zahlen ist dann die letzte Zahl durch die geteilt worden ist. Als Beispiel sollen hierbei die (vergleichsweise großen) Zahlen \(17262\) und \(8580\) dienen. Wir rechnen:
\begin{align*}
17262 \div 8580 &=2 \ \textrm{Rest} \ 102 \\
8580 \div 102 &=  84 \ \textrm{Rest} \ 12 \\
102 \div12 &= 8 \ \textrm{Rest} \ 6 \\
12 \div 6 &= 2 \ \textrm{Rest} \ 0 \\
\end{align*}

Das bedeutet, der \(\textrm{ggT}\) von \(17262\) und \(8580\) ist \(6\).
Es gibt zwar keine Vergleichbare Methode zur Bestimmung des \(\textrm{kgV}\), aber wegen der Formel \(\textrm{ggT}(a,b) \cdot \textrm{kgV}(a,b)=a \cdot b\) lässt sich das \(\textrm{kgV}\) aus \(17262\) und \(8580\) dennoch berechnen, man hat:
\begin{align*}\textrm{kgV}(17262,8580)=17262 \cdot 8580 \div \textrm{ggT}(17626,8580)= 24684660.\end{align*}