Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches

Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache

In der Lektion über Teilbarkeit und Division mit Rest wurde die Relation $d \mid a$ zwischen zwei natürlichen Zahlen untersucht. Betrachtet man zwei Zahlen zugleich, so interessieren die Teiler, die sie gemeinsam haben, und die Vielfachen, die sie teilen. Jedes Paar natürlicher Zahlen $a$ und $b$ hat mindestens einen gemeinsamen Teiler, nämlich die $1$, und höchstens endlich viele, weil kein Teiler von $a$ größer ist als $a$; es hat außerdem unendlich viele gemeinsame Vielfache, darunter das Produkt $ab$. Ist dem so, dann ist die folgende Definition sinnvoll.

Definition (größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches). Der größte gemeinsame Teiler zweier natürlicher Zahlen $a$ und $b$, geschrieben $\operatorname{ggT}(a, b)$, ist die größte natürliche Zahl, die beide teilt. Das kleinste gemeinsame Vielfache, geschrieben $\operatorname{kgV}(a, b)$, ist die kleinste natürliche Zahl, die ein Vielfaches von beiden ist.

Das zweite ist das kleinste Element einer nichtleeren Menge natürlicher Zahlen, das nach dem Wohlordnungsprinzip existiert. Der erste ist das größte Element der Menge der gemeinsamen Teiler, die nicht leer und durch $a$ beschränkt ist; dass eine nichtleere, nach oben beschränkte Menge natürlicher Zahlen ein Maximum hat, folgt ebenfalls aus der Wohlordnung: Die Menge ihrer oberen Schranken ist nicht leer und hat ein Minimum $M$, und $M$ gehört zur Menge, denn sonst wäre jedes Element kleiner als $M$ und, da es keine natürlichen Zahlen zwischen $M - 1$ und $M$ gibt, nicht größer als $M - 1$, das eine obere Schranke kleiner als $M$ wäre (ist $M = 1$, so ist die Menge $\{1\}$ und enthält $M$). Zum Beispiel sind die gemeinsamen Teiler von $12$ und $18$ die Zahlen $1$, $2$, $3$ und $6$, und ihre gemeinsamen Vielfachen sind $36$, $72$, $108$ und so weiter:

Aus der Definition folgen unmittelbar einige Sonderfälle: $\operatorname{ggT}(a, 1) = 1$ und $\operatorname{kgV}(a, 1) = a$; $\operatorname{ggT}(a, a) = \operatorname{kgV}(a, a) = a$; und, wenn $a$ die Zahl $b$ teilt, dann $\operatorname{ggT}(a, b) = a$ und $\operatorname{kgV}(a, b) = b$. Beide Operationen sind außerdem symmetrisch: Die Reihenfolge der Zahlen ändert das Ergebnis nicht.

Berechnung mit der Primfaktorzerlegung

Nach dem Fundamentalsatz der Arithmetik lässt sich jede natürliche Zahl größer als $1$ eindeutig in Primfaktoren zerlegen. Es ist zweckmäßig, $a$ und $b$ mit denselben Primzahlen $p_1, \ldots, p_k$ zu schreiben und für die Primzahlen, die nur in einer der beiden vorkommen, den Exponenten null zuzulassen:

Eine natürliche Zahl $d$ teilt $a$ genau dann, wenn in ihrer Zerlegung keine anderen Primzahlen als die von $a$ vorkommen, jede mit einem Exponenten, der nicht größer ist als ihr Exponent in $a$. Daraus folgt, dass $d$ zugleich $a$ und $b$ teilt, wenn der Exponent jeder Primzahl in $d$ keinen der beiden Exponenten übersteigt; den größten gemeinsamen Teiler erhält man daher, indem man für jede Primzahl den kleineren der beiden Exponenten nimmt. Ebenso ist $m$ ein gemeinsames Vielfaches, wenn der Exponent jeder Primzahl in $m$ beide erreicht, und das kleinste gemeinsame Vielfache nimmt für jede Primzahl den größeren der beiden Exponenten. Zum Beispiel:

Das Verfahren ist klar, setzt aber voraus, dass man faktorisieren kann, und große Zahlen zu faktorisieren ist sehr aufwendig: Kein schnelles Verfahren dafür ist bekannt. Der Algorithmus des folgenden Abschnitts berechnet den größten gemeinsamen Teiler ohne Faktorisieren, allein mit Divisionen.