Mathematik: Zahlentheorie: Größter gemeinsamer Teiler

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Dieses Kapitel ist noch unter Konstruktion und kann Lücken und Fehler enthalten.



Kapitel 2: Größter gemeinsamer Teiler

Überblick über das Kapitel:

größter gemeinsamer
Teiler
kleinstes gemeinsames
Vielfaches
Euklidischer
Algorithmus
Darstellung
als Linearkombination
nachzuliefernder
Beweis

Hat man eine ganze Zahl gegeben, so kann man eine Liste mit allen Teilern dieser Zahl erstellen. Hat man eine weitere ganze Zahl, zu der man ebenfalls eine solche Liste erstellt hat, so stellt sich die Frage nach Teilern, die in beiden Listen vorkommen, den gemeinsamen Teilern. Da jede Zahl teilt, gibt es immer solche gemeinsame Teiler, und die ist auch immer der kleinste der gemeinsamen Teiler. Wesentlich spannender ist die Frage nach dem größten gemeinsamen Teiler.

Eine, in gewissem Sinne duale Eigenschaft zum größten gemeinsamen Teiler zweier Zahlen, ist das kleinste gemeinsame Vielfache, welches wir uns kurz anschauen wollen, bevor wir dazu übergehen, uns zu fragen, wie man den größten gemeinsamen Teiler berechnet. Etwa 300 Jahre vor Christus fand Euklid ein Verfahren zur Bestimmung des größten gemeinsamen Teilers, welches auch heute noch fast ausschließlich benutzt wird, nämlich den nach ihm benannten Euklidschen Algorithmus.

Erweitert man den Euklidschen Algorithmus ein wenig, so erhält man eine Darstellung des größten gemeinsamen Teilers als Linearkombination aus den beiden gegebenen Zahlen. Diese wollen wir dann nutzen, um den im ersten Kapitel versprochenen Beweis nachzuliefern, dass jede unzerlegbare Zahl eine Primzahl ist.

Größter gemeinsamer Teiler[Bearbeiten]

Definition
Eine ganze Zahl heißt ein größter gemeinsamer Teiler zweier ganzer Zahlen und , wenn gilt:
  • Wenn ein (weiterer) Teiler von und von ist, so gilt .
Man schreibt dann oder, wenn keine Verwechslungen zu befürchten sind, . → Wikipedia:größter gemeinsamer Teiler
Ist der größte gemeinsame Teiler zweier Zahlen und gleich , so sagt man, und sind teilerfremd. → Wikipedia:Teilerfremd

Bei der Definition des größten gemeinsamen Teilers fällt zweierlei auf: Zum einen wird nicht, wie der Name suggeriert, verlangt, dass der größte gemeinsame Teiler größer als alle anderen gemeinsamen Teiler ist. Stattdessen soll er ein Vielfaches aller gemeinsamen Teiler sein. Der Grund, warum wir das so definieren, liegt, wie schon bei den Primzahlen, darin begründet, dass diese Definition hier (fast) gleichwertig ist, sich aber auf beliebige Ringe verallgemeinern lässt. Bei beliebigen Ringen haben wir nämlich möglicherweise keine Größer-Beziehung mehr. Noch allgemeiner kommt hinzu, dass sich viele Fragen bereits ordnungstheoretisch behandeln lassen, und die getroffene Definition exakt der des Infimums zweier Elemente in der jeweiligen nach Teilbarkeit prägeordneten Menge entspricht.

Das zweite Auffällige ist das Wörtchen ein. Dies hängt damit zusammen, dass wir oben "fast" geschrieben haben. Der größte gemeinsame Teiler ist nach dieser Definition nämlich nicht unbedingt eindeutig. Es ist sowohl als auch ein größter gemeinsamer Teiler von und . (Wer sich daran stört, dass ein größter gemeinsamer Teiler sein soll, wo doch größer ist, kann sich vorstellen, vom betragsmäßig größten gemeinsamen Teiler zu sprechen.) Dass es hier zwei größte gemeinsame Teiler gibt, liegt daran, dass wir hier schon streng genommen eine Verallgemeinerung betrachten, nämlich die auf den ganzen Zahlen und nicht nur auf den natürlichen Zahlen. Bei anderen Ringen kann es sogar vorkommen, dass zwei Zahlen gar keinen größten gemeinsamen Teiler mehr besitzen.

Noch ein Wort zur Schreibweise : Da der größte gemeinsame Teiler einer Zahl nicht unbedingt eindeutig bestimmt zu sein braucht, handelt es sich streng genommen auch nicht um eine Gleichheitsrelation. Korrekter müsste man also schreiben , das macht aber kaum jemand.

Beispiel:

  • (aber auch: )


Den größten gemeinsamen Teiler kann man auch von mehr als zwei Zahlen definieren. Man macht das dann üblicherweise induktiv, indem man setzt.

Gleiches gilt auch für die Teilerfremdheit. Hier muss man aber etwas aufpassen, damit man keinen Denkfehler macht: Die Zahlen , und sind teilerfremd, da ist. und sind aber nicht teilerfremd, da sie den gemeinsamen Teiler haben. Möchte man ausdrücken, dass die Primfaktoren aller beteiligten Zahlen verschieden sind, so sagt man die Zahlen sind paarweise teilerfremd.


Kennt man die Primfaktorzerlegung von und , so lässt sich daraus leicht der größte gemeinsame Teiler berechnen.

Satz
Seien und die Primfaktorzerlegungen von und . Dann ist .
Beweis
Da
 
und
 
ist offensichtlich ein gemeinsamer Teiler von und .

Es bleibt zu zeigen, dass jeder weitere gemeinsame Teiler ein Teiler von ist. Rest vom Beweis fehlt noch.

Beispiel:

Ist und . Dann sind die Primfaktorzerlegungen von :
und der größte gemeinsame Teiler ist

Kleinstes gemeinsames Vielfaches[Bearbeiten]

Definition
Die natürliche Zahl heißt kleinstes gemeinsames Vielfaches zweier natürlicher Zahlen und , wenn gilt:
  • Wenn ein (weiteres) gemeinsames Vielfaches von und von ist, so gilt .
Man schreibt dann .

Beispiel:

Analog zum größten gemeinsamen Teiler kann man auch das kleinste gemeinsame Vielfache für mehr als zwei Zahlen definieren.


Satz
Kleinstes gemeinsames Vielfaches und größter gemeinsamer Teiler hängen durch folgende Gleichung zusammen:
Beweis
Primfaktorzerlegung folgt.

Division mit Rest[Bearbeiten]

Sind ganze Zahlen und mit gegeben, so gibt es eindeutig bestimmte ganze Zahlen und mit und .

Beweis
Existenz: Sei die Menge aller nicht-negativen Zahlen der Form . Diese Menge enthält ein kleinstes Element . Für dieses gilt , da sonst das kleinere Element ebenfalls in liegen würde.

Eindeutigkeit: Übung.

heißt der ganzzahlige Quotient, der Rest der ganz-zahligen Division von durch . Im folgenden wird auch als geschrieben, also .

Bemerkung:

Es gilt . Denn jeder gemeinsame Teiler von und teilt auch , und umgekehrt teilt jeder gemeinsame Teiler von und auch .

Beispiele:

Euklidischer Algorithmus[Bearbeiten]

Der moderne Euklidische Algorithmus wir mittels einer Division mit Rest ausgeführt. Er beginnt mit den Zahlen und deren größter gemeinsamer Teiler bestimmt wird. Also :

, wie bei der Division mit Rest eingeführt, jedoch um einen Index ergänzt. Mit der Festlegung und ergibt sich bis zum Abbruchkriterium folgende Darstellung:
Der Divisor ist dann der größte gemeinsame Teiler .

Beispiele:

Der größte gemeinsame Teiler von und wird mit Euklidischen Algorithmus berechnet :
Also ist der größte gemeinsame Teiler von und .
Der größte gemeinsame Teiler von und wird wie folgt berechnet :
Demnach sind und teilerfremd, bzw. haben keinen größten gemeinsamen Teiler.


Darstellung des ggT als Linearkombination[Bearbeiten]

Es gibt ganze Zahlen r und s, sodass gilt:

ra + sb = ggT(a,b).

r und s lassen sich mit Hilfe des erweiterten Euklidischen Algorithmus bestimmen. Wir erläutern das anhand eines Beispiels:

ggT(19,15) = ggT(4,15) = ggT(4,3) = ggT(1,3) = ggT(1,0) = 1, und

4 = 19 - 15

3 = 15 - 3*4 = 15 - 3*(19 - 15) = 4*15 - 3*19

1 = 4 - 3 = (19 - 15) - (4*15 - 3*19) = 4*19 - 5*15

Beweis, dass jede unzerlegbare Zahl eine Primzahl ist[Bearbeiten]

Im ersten Kapitel haben wir behauptet, dass unzerlegbare Zahlen und Primzahlen das Gleiche sind, haben aber bisher nur gezeigt, dass jede Primzahl eine unzerlegbare Zahl ist. Mit dem jetzt vorhandenen Wissen, können wir die Umkehrung beweisen:

Satz
Jede unzerlegbare Zahl ist eine Primzahl.
Beweis
Sei eine unzerlegbare Zahl und gelte . Angenommen, teilt nicht, so bedeutet dies, dass der größte gemeinsame Teiler von und gleich sein muss, da nur zwei Teiler hat und selbst kein Teiler von ist. Das ist aber gleichbedeutend mit der Aussage, dass es ganze Zahlen und gibt, mit . Multiplizieren wir diese Gleichung mit so ergibt sich . Da , teilt die linke Seite der Gleichung, also auch .
→  voriges Kapitel
→  Zurück zum Inhaltsverzeichnis "Zahlentheorie"
→  Zur Inhaltsübersicht