Mathematik: Zahlentheorie: Größter gemeinsamer Teiler

Aus Wikibooks

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 Zahl gegeben, so kann man eine Liste mit allen Teilern dieser Zahl erstellen. Hat man eine weitere 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 1 jede Zahl teilt, gibt es immer solche gemeinsame Teiler, und die 1 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.

[Bearbeiten] Größter gemeinsamer Teiler

Definitionen:

Eine ganze Zahl d heißt ein größter gemeinsamer Teiler zweier ganzer Zahlen a und b, wenn gilt:

d | a
d | b
Wenn c ein (weiterer) Teiler von a und von b ist, so gilt c | d.

Man schreibt dann d = ggT(a,b) oder, wenn keine Verwechslungen zu befürchten sind, d = (a,b). → Wikipedia:größter gemeinsamer Teiler

Ist der größte gemeinsame Teiler zweier Zahlen a und b gleich 1, so sagt man, a und b 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.

Das Zweite was auffällt ist das Wörtchen ein. Damit hängt auch zusammen, dass wir oben "fast" geschrieben haben. Der größte gemeinsame Teiler ist nach dieser Definition nämlich nicht unbedingt eindeutig. Es ist sowohl 5 als auch -5 ein größter gemeinsamer Teiler von 15 und 25. (Wer sich daran stört, dass -5 ein größter gemeinsamer Teiler sein, soll, wo 5 doch größer ist, kann sich vorstellen, vom betragsmäßig größten gemeinsamen Teiler zu sprechen.) Das 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 d = ggT(a,b): 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 d∈ggT(a,b), das macht aber kaum jemand.

Beispiele:

(24,42)=6 (aber auch: (24,42)=-6)
(24,12)=12
(17,13)=1

Den größten gemeinsamen Teiler kann man auch von mehr als zwei Zahlen definieren. Man macht das dann üblicherweise induktiv, indem man ggT(a₁,...,a_n) := ggT(ggT(a₁,...,a_n-1),n) setzt.

Gleiches gilt auch für die Teilerfremdheit. Hier muss man aber etwas aufpassen, damit man keinen Denkfehler macht: Die Zahlen 6, 10 und 15 sind teilerfremd, da ggT(6,10,15)=ggT(2,15)=1 ist. 6 und 10 sind aber nicht teilerfremd, da sie den gemeinsamen Teiler 2 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 a und b, so lässt sich daraus leicht der größte gemeinsame Teiler berechnen:

Satz Seien $a = \prod_p p^{\nu_{p,a}}$ und $b = \prod_p p^{\nu_{p,b}}$ die Primfaktorzerlegungen von a und b. Dann ist $ggT(a,b) = \prod_p p^{min(\nu_{p,a},\nu_{p,b})}$ .

Beweis: Da

$a = \prod_p p^{min(\nu_{p,a},\nu_{p,b})}\cdot\prod_p p^{(\nu_{p,a}-min(\nu_{p,a},\nu_{p,b}))}$

und

$b = \prod_p p^{min(\nu_{p,a},\nu_{p,b})}\cdot\prod_p p^{(\nu_{p,b}-min(\nu_{p,a},\nu_{p,b}))}$

ist $d:=\prod_p p^{min(\nu_{p,a},\nu_{p,b})}$ offensichtlich ein gemeinsamer Teiler von a und b. Es bleibt zu zeigen, dass jeder weitere gemeinsame Teiler c ein Teiler von d ist. Rest vom Beweis fehlt noch.

[Bearbeiten] Kleinstes gemeinsames Vielfaches

Definitionen: Die natürliche Zahl m heißt kleinstes gemeinsames Vielfaches zweier natürlicher Zahlen a und b, wenn gilt:

a | m
b | m
Wenn c ein (weiteres) gemeinsames Vielfaches von a und von b ist, so gilt m | c.

Man schreibt dann m = kgV(a,b).

Beispiel:

kgV(10,6)=30
kgV(5,7)=35
kgv(10,20)=20

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:

a·b=ggT(a,b)·kgV(a,b)

Beweis: Primfaktorzerlegung.

[Bearbeiten] Division mit Rest

Sind ganze Zahlen a und b mit b ≠ 0 gegeben, so gibt es eindeutig bestimmte ganze Zahlen q und r mit a=qb+r und 0<=r<b.

Beweis:

Existenz: Sei M die Menge aller nicht-negativen Zahlen der Form a-qb. Diese Menge enthält ein kleinstes Element r. Für dieses gilt r<b, da sonst das kleinere Element r-b=a-(q+1)b ebenfalls in M liegen würde.

Eindeutigkeit: Übung.

q heißt der Quotient, r der Rest der ganz-zahligen Division von a durch b. Im folgenden wird r auch als a mod b geschrieben.

Bemerkung: Es gilt ggT(a,b)=ggT(r,b). Denn jeder gemeinsame Teiler von a und b teilt auch r=a-qb, und umgekehrt teilt jeder gemeinsame Teiler von r und b auch a=qb+r.

[Bearbeiten] Euklidischer Algorithmus

Eingabe: ganze Zahlen a und b

while b≠0

r := a mod b;

a := b;

b := r;

Ausgabe: Der größte gemeinsame Teiler von a und b steht jetzt in a.

Beweis:

Der Algorithmus endet, da b nach dem ersten Schleifendurchlauf stets nicht-negativ ist, und jedesmal kleiner wird.

Bei jedem Schleifendurchlauf bleibt der größte gemeinsame Teiler von a und b erhalten.

Primzahlen sind Zahlen, die nur durch eins und sich selbst teilbar sind

[Bearbeiten] Darstellung des ggT als Linearkombination

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

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

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 n eine unzerlegbare Zahl und gelte n | ab. Angenommen, n teilt a nicht, so bedeutet dies, dass der größte gemeinsame Teiler von a und n gleich 1 sein muss, da n nur zwei Teiler hat und n selbst kein Teiler von a ist. Das ist aber gleichbedeutend mit der Aussage, dass es ganze Zahlen s und t gibt, mit sa+tn=1. Multiplizieren wir diese Gleichung mit b so ergibt sich sab+tnb=b. Da n | ab, teilt n die linke Seite der Gleichung, also auch b.