ggT und kgV

Der größte gemeinsame Teiler ggT

Für eine Menge ganzer positiver Zahlen {a₁, a₂,..., a_n} ist der größte gemeinsame Teiler die größte natürliche Zahl, die alle Zahlen der Menge teilt. Hierfür benötigen wir Kenntnisse der Primfaktorzerlegung, also der Art und Weise, wie man jede beliebige natürliche Zahl in ihre Primfaktoren zerlegt. Ist dies für alle Zahlen der Menge geschehen, so können wir den größten gemeinsamen Teiler ablesen, indem wir einfach von jedem Primfaktor, welcher in jeder der Darstellungen der einzelnen Zahlen vorkommt, die insgesamt niedrigste Potenz nehmen und diese Zahlen multiplizieren. Wir bezeichnen den größten gemeinsamen Teiler mit ggT(a₁, a₂,..., a_n).

Beispiele für zwei Zahlen:

• Nehmen wir beispielsweise die Zahlen 75 und 35, so können wir diese beiden Zahlen in ihre Primfaktoren zerlegen:
  • 75 = 3·5²
  • 35 = 5·7
  Für den größten gemeinsamen Teiler (den wir von jetzt an generell mit ggT abkürzen werden) erhalten wir also ggT(75,35) = 5.
• Betrachten wir die Zahlen 81 und 9. Wie man bereits sehen kann, ist 9 ein Teiler von 81, und es sollte somit auch nicht weiter verwundern, dass der ggT(81,9) = 9 ist. Wir wollen das Beispiel trotzdem komplett durchrechnen.
  • 81 = 3⁴
  • 9 = 3²
  Damit ist ggT(81,9) = 3² = 9.
  Man sieht also leicht ein, dass in dem Fall, wenn eine der Zahlen Teiler der anderen ist, diese auch gleichzeitig den ggT darstellt.
• Wählen wir die Zahlen 27 und 16, so gilt:
  • 27 = 3³
  • 16 = 2⁴
  Für die Berechnung des ggT haben wir also überhaupt keinen gemeinsamen Teiler. In diesem Fall gilt ggT(27,16) = 1. Zahlen, die den ggT 1 haben, nennen wir auch teilerfremd.

Bemerkungen:

Dies folgt eigentlich nicht aus unser Definition, da wir in diesem Fall überhaupt keine Vorschrift zur Berechnung des ggT haben. Das liegt daran, dass die von uns gewählte Definition nicht vollkommen korrekt ist, dafür jedoch weitaus anschaulicher als die weiter unten angegebene allgemeine mathematische Definition und mit der Zusatzbedingung, dass man im Falle teilerfremder Zahlen den ggT auf 1 setzt, wird die Definition auch vervollständigt.
Die eigentlich korrekte Definition nimmt zur Berechnung des ggT nicht nur alle in jeder Zahl auftretenden Primfaktoren, sondern alle insgesamt auftretenden Primfaktoren her und berechnet den ggT dann auf die gleiche Art und Weise wie bisher.
Die zusätzlich auftretenden Primfaktoren verändern den ggT dann nicht, da sie ja mit Potenz 0 in der Berechnung auftreten, sie sind ja schließlich nicht in allen Zahlen der Menge vorhanden. Als Verbesserung erhält man aber automatisch einen ggT von 1 bei teilerfremden Zahlen.
In unseren Beispielen wäre also:

• ggT(75,35) = 3⁰·5¹·7⁰ = 1·5·1 = 5
• ggT(27,16) = 3⁰·2⁰ = 1·1 = 1

Wie man erkennt bekommt man eventuell einfach eine ganze Reihe von Einsen in das Produkt, was die Übersichtlichkeit doch nicht gerade fördert.
Weiter unten werden wir, wie bereits erwähnt, noch eine mathematisch korrekte Formel für den allgemeinen ggT angeben, welche alle diese Fälle berücksichtigt, dafür jedoch - zumindest auf den ersten Blick - ziemlich kompliziert aussieht.

Beispiel für mehr als zwei Zahlen:

Betrachten wir die Zahlen a₁=15.400, a₂=7875 und a₃=3850, so erhalten wir:

• 15.400 = 2³·5²·7·11
• 7875 = 3²·5³·7
• 3850 = 2·5³·7·11

Somit gilt: ggT(15.400,7875,3850) = 5²·7 = 175.

Allgemeine mathematische Definition:

Haben wir ganze positive Zahlen a₁, a₂,..., a_n gegeben mit einer jeweiligen Primfaktorzerlegung

so ist der größte gemeinsame Teiler definiert als

Das kleinste gemeinsame Vielfache kgV

Auf ähnliche Art und Weise wie bereits oben der größte gemeinsame Teiler eingeführt wurde, werden wir nun das kleinste gemeinsame Vielfache (von jetzt an nur noch kgV genannt) definieren.
Auch hierbei ist eigentlich schon dem Namen zu entnehmen, um was es sich handelt.
Zu gegebenen ganzen positiven Zahlen a₁, a₂,..., a_n suchen wir die kleinste natürliche Zahl, die ein Vielfaches von allen a_i ist. Dabei betrachen wir wieder die jeweiligen Primfaktorzerlegungen der einzelnen a_i und bestimmen das kgV als Produkt aller auftretenden Primfaktoren mit ihrer jeweils größten auftretenden Potenz.
Die Schreibweise ist dann kgV(a₁, a₂,..., a_n).

Beispiele für zwei Zahlen:

Wir betrachten einfach die gleichen Zahlenbeispiele wie beim ggT:

• Wie schon gesehen erhalten wir bei den Zahlen 75 und 35 die Primfaktorzerlegungen
  • 75 = 3·5²
  • 35 = 5·7
  Somit ist das kgV gegeben durch kgV(75,35) = 3·5²·7 = 525.
• Für 81 und 9 haben wir die Primfaktorzerlegungen
  • 81 = 3⁴
  • 9 = 3²
  Damit ist kgV(81,9) = 3⁴ = 81. Wie man an diesem Beispiel erkennt, gilt für das kgV im Falle, dass eine Zahl ein Vielfaches der anderen ist, dass auch das kgV schon durch dieses Vielfache gegeben ist.
• Im Beispiel der teilerfremden Zahlen 27 und 16 haben wir die Primfaktorzerlegungen
  • 27 = 3³
  • 16 = 2⁴
  Wir erhalten kgV(27,16) = 3³·2⁴ = 27·16 = 432. Man sieht hier, dass bei teilerfremden Zahlen das kgV genau das Produkt der Zahlen ist.

Bemerkungen:

Wie man an den Beispielen sehr schön gesehen hat, ergibt sich bei unserer intuitiven Definition - im Gegensatz zum ggT - kein Problem beim Spezialfall der teilerfremden Zahlen.
Die gegebene Definition ist also diesmal vollständig äquivalent zur allgemeinen mathematischen Definition, die wir auch hier wieder weiter unten noch angeben werden.

Beispiel für mehrere Zahlen:

Auch hier wählen wir wieder die Zahlen a₁=15.400, a₂=7875 und a₃=3850 mit den Primfaktorzerlegungen

• 15.400 = 2³·5²·7·11
• 7875 = 3²·5³·7
• 3850 = 2·5³·7·11

Als kGV erhalten wir also: kgV(14.500,7875,3850) = 2³·3²·5³·7·11 = 8·9·125·7·11 = 693.000.

Allgemeine mathematische Definition:

Haben wir ganze positive Zahlen a₁, a₂,..., a_n gegeben mit einer jeweiligen Primfaktorzerlegung

so ist das kleinste gemeinsame Vielfache kgV definiert als

Zusammenhang zwischen ggT und kgV:

An dieser Stelle wollen wir noch darauf hinweisen, dass für je zwei natürliche Zahlen a, b gilt:
a·b = ggT(a,b)·kgV(a,b).

Diese Behauptung wollen wir an dieser Stelle zwar nicht beweisen, jedoch zumindest an unseren Beispielen überprüfen:

• 75·35 = 2625 und ggT(75,35)·kgV(75,35) = 5·525 = 2625
• 81·9 = 729 und ggT(81,9)·kgV(81,9) = 9·81 =729
• 27·16 = 432 und ggT(27,16)·kgV(27,16) = 1·432 = 432

Man sollte jedoch beachten, dass sich diese Aussage auf jeweils zwei natürliche Zahlen bezieht. Nimmt man unser Beispiel mit mehreren Zahlen a₁=15.400, a₂=7875 und a₃=3850, so erhält man:

• 14.500·7875·3850 = 439.621.875.000
• ggT(14.500,7875,3850)·kgV(14.500,7875,3850) = 175·693.000 = 121.275.000

was offensichtlich nicht das gleiche Ergebnis ist.

Effiziente Berechnung des ggT mit dem Euklidischen Algorithmus

Der größte gemeinsame Teiler von zwei Zahlen kann sehr effizient berechnet werden mit Hilfe des Euklidischen Algorithmus, der zu den ältesten Algorithmen der Mathematik zählt. Hierzu führt man sukzessive Division mit Rest durch. Zum besseren Verständnis stellen wir den Algorithmus zunächst an einem Beispiel vor:

• Gesucht ist der ggT von 128 und 56:
  
  Wir teilen sukzessive mit Rest, bis irgendwann der Rest 0 wird:
  
  
  Der Divisor, bei dem die Division aufgeht, ist der ggT. Somit beträgt der ggT von 128 und 56 gerade 8.

Allgemein wird der Algorithmus auf zwei gegebene Ganzzahlen \(r_0,r_1 \in \N,\ r_0>r_1\) wie folgt angewendet: Die größere Ganzzahl r₀ wird durch die kleinere Ganzzahl r₁ mit Rest r₂ dividiert. Ist der erhaltene Rest r₂ nicht 0, so wird eine Ganzzahldivision der kleineren Ganzzahl r₁ durch den Rest r₂ durchgeführt, wobei man einen neuen Rest r₃ erhält. Diese Vorgehensweise wird so lange wiederholt, bis die Division durch den Rest r_n+1 der vorherigen Zeile aufgeht. Dann ist dieser Rest r_n+1 der ggT der Zahlen r₀ und r₁.

⇒ ggT(r₀ , r₁) = r_n+1

Nun kann man sich zunächst fragen, warum der Algorithmus überhaupt irgendwann abbricht. Das liegt daran, dass bei einer Ganzzahldivision der Rest immer kleiner ist als die Zahl, durch die geteilt wird. Das bedeutet \[ r_1 > r_2 > r_3 > \ldots > r_n > r_{n+1} > 0\] Somit werden die Zahlen im Algorithmus in jeder neuen Zeile immer kleiner und kleiner. Der Algorithmus muss also abbrechen, da mit endlich großen Zahlen gestartet wird und die Reste nicht kleiner als 0 werden können.

Dass der Euklidische Algorithmus wirklich den ggT von r₀ und r₁ berechnet, kann man sich wie folgt klarmachen: Aus der 1. Zeile des Algorithmus \[ r_0 = c_1 \cdot r_1 + r_2 \] folgt, dass alle gemeinsamen Teiler von r₀ und r₁ auch Teiler von r₂ sein müssen, da c₁ eine Ganzzahl ist. Dies gilt auch für den ggT(r₀ , r₁), daher folgt: \[ {\rm ggT}(r_0,r_1) = {\rm ggT}(r_1, r_2) \] Dieselbe Argumentation lässt sich auf Zeile 2 und alle weiteren bis zur vorletzten Zeile anwenden: \[ {\rm ggT}(r_0,r_1) = {\rm ggT}(r_1, r_2) = {\rm ggT}(r_2, r_3) = \ldots = {\rm ggT}(r_{n-1}, r_n) = {\rm ggT}(r_n, r_{n+1}) \] Aus der letzten Zeile \[ r_n = c_{n+1} \cdot r_{n+1} \] folgt, dass der ggT(r_n , r_n+1 ) = r_n+1 ist, da r_n+1 die Zahl r_n teilt. Daher gilt insgesamt \[ {\rm ggT}(r_0,r_1) = r_{n+1} \] und dies wollten wir gerade zeigen.

Links

Leider konnten wir keine interessanten Seiten zu diesem Thema finden. Sie haben eine Seite zum Thema? Schreiben Sie uns! (mail[at]mathematik.de)