Mathematik: Zahlentheorie: Größter gemeinsamer Teiler

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 TeilerBearbeiten

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 VielfachesBearbeiten

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 RestBearbeiten

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 AlgorithmusBearbeiten

Der moderne Euklidische Algorithmus wird 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 LinearkombinationBearbeiten

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 istBearbeiten

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  .