Quelltext der Seite Mathematik: Zahlentheorie: Größter gemeinsamer Teiler

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

__NOTOC__
<div style="font-size:180%; text-align:center;">
'''Kapitel 2: Größter gemeinsamer Teiler'''
</div>
{| class=rimage
 |
<div style="border:1pt solid #8080ff;padding:0.5em;background-color:#F0F0FF">
'''Überblick über das Kapitel:'''     
{| style="background-color:#F0F0FF"
 | <div style="border:1pt solid #000000;padding:0.5em;background-color:#8080ff">größter gemeinsamer<br>Teiler</div>
 | &rarr;
 | <div style="border:1pt solid #000000;padding:0.5em;background-color:#8080ff">kleinstes gemeinsames<br>Vielfaches</div>
 |-
 | &darr;
 |-
 | <div style="border:1pt solid #000000;padding:0.5em;background-color:#80ff80">Euklidischer<br>Algorithmus</div>
 |-
 | &darr;
 |-
 | <div style="border:1pt solid #000000;padding:0.5em;background-color:#8080ff">Darstellung<br>als Linearkombination</div> 
 |-
 | &darr;
 |-
 | <div style="border:1pt solid #000000;padding:0.5em;background-color:#ffd080">nachzuliefernder<br>Beweis</div>
 |-
 |}
</div>
 |}
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 <math> 1 </math> jede Zahl teilt, gibt es immer solche gemeinsame Teiler, und die <math> 1 </math> 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 [[Mathematik: Zahlentheorie: Fundamentalsatz der Arithmetik|ersten Kapitel]] versprochenen Beweis nachzuliefern, dass jede unzerlegbare Zahl eine Primzahl ist.

==Größter gemeinsamer Teiler==

; Definition: 
: Eine ganze Zahl <math> d </math> heißt ein ''größter gemeinsamer Teiler'' zweier ganzer Zahlen <math> a </math> und <math> b </math>, wenn gilt:
::*<math> d \ | \ a </math>
::*<math> d \ | \ b</math>
::*Wenn <math> c </math> ein (weiterer) Teiler von <math> a </math> und von <math> b </math> ist, so gilt <math> c \ | \ d </math>.
: Man schreibt dann <math> d \ := \ ggT(a , b) </math> oder, wenn keine Verwechslungen zu befürchten sind, <math> d \ := \ (a ,b) </math>. ''&rarr;&nbsp;[[w:größter gemeinsamer Teiler|Wikipedia:größter gemeinsamer Teiler]]''
: Ist der größte gemeinsame Teiler zweier Zahlen <math> a </math> und <math> b </math> gleich <math> 1 </math>, so sagt man, <math> a </math> und <math> b </math> sind ''teilerfremd''. ''&rarr;&nbsp;[[w: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 <math> 5 </math> als auch <math> -5 </math> ein größter gemeinsamer Teiler von <math> 15 </math> und <math> 25 </math>. (Wer sich daran stört, dass <math> -5 </math> ein größter gemeinsamer Teiler sein soll, wo <math> 5 </math> 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 <math> d \ = \ ggT(a , b) </math>: 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 <math> d \isin ggT(a , b) </math>, das macht aber kaum jemand.

Beispiel: 
:* <math> ggT (24, 42) = 6 </math> (aber auch: <math> ggT(24 , 42) = -6 </math>) 

:* <math> ggT (24 , 12) = 12 </math>

:* <math> ggT (17 , 13) = 1 </math>


Den größten gemeinsamen Teiler kann man auch von mehr als zwei Zahlen definieren. Man macht das dann üblicherweise induktiv, indem man <math> ggT (a_1, ..., a_n) \ := \ ggT ( ggT (a_1, ... , a_{n-1} ), a_n) </math> setzt.

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

; Satz:
: Seien <math>a = \prod_{p \isin \mathbb{P}} p^{\nu_{p,a}}</math> und <math>b = \prod_{p \isin \mathbb{P}} p^{\nu_{p,b}}</math> die Primfaktorzerlegungen von <math> a </math> und <math> b </math>. Dann ist <math>ggT(a,b) = \prod_{p \isin \mathbb{P}} p^{min(\nu_{p,a},\nu_{p,b})}</math>.

; Beweis: 
: Da <math>a = \prod_{p \isin \mathbb{P}} p^{min(\nu_{p,a},\nu_{p,b})} \cdot \prod_{p \isin \mathbb{P}} p^{(\nu_{p,a}-min(\nu_{p,a},\nu_{p,b}))}</math>
: &nbsp;
: und <math>b = \prod_{p \isin \mathbb{P}} p^{min(\nu_{p,a},\nu_{p,b})} \cdot \prod_{p \isin \mathbb{P}} p^{(\nu_{p,b}-min(\nu_{p,a},\nu_{p,b}))}</math>
: &nbsp;
: ist <math>d:=\prod_{p \isin \mathbb{P}} p^{min(\nu_{p,a},\nu_{p,b})}</math> offensichtlich ein gemeinsamer Teiler von <math>a </math> und <math>b </math>. 

Es bleibt zu zeigen, dass jeder weitere gemeinsame Teiler <math>c\,</math> ein Teiler von <math>d\,</math> ist. ''Rest vom Beweis fehlt noch.''

Beispiel: 
: Ist <math> a = 5 \cdot 10^5 </math> und <math> b = 970 </math>. Dann sind die Primfaktorzerlegungen von <math> a, b </math>:
: <math> a = 5 \cdot 10^5 = 5 \cdot 2^5 \cdot 5^5 = 2^5 \cdot 5^6 </math>
: <math> b = 970 = 2 \cdot 5 \cdot 97 </math>
: und der größte gemeinsame Teiler ist 
: <math> ggT ( a , b ) = \prod_{ p = \lbrace 2 , 5 , 97 \rbrace } p^{ min (  \nu_{p,a} , \nu_{p,b} } ) \ = \ 2^1 \cdot 5^1 \cdot 97^0 \ = \ 10 </math>

==Kleinstes gemeinsames Vielfaches==

; Definition: 
: Die natürliche Zahl <math> m </math> heißt ''kleinstes gemeinsames Vielfaches'' zweier natürlicher Zahlen <math> a </math> und <math> b </math>, wenn gilt:
:* <math> a \ | \ m </math>
:* <math> b \ | \ m </math>
:* Wenn <math> c </math> ein (weiteres) gemeinsames Vielfaches von <math> a </math> und von <math> b </math> ist, so gilt <math> m \ | \ c </math>. 
: Man schreibt dann <math> m \ = \ kgV (a , b) </math>. 

Beispiel:
:* <math> kgV (10 , 6) = 30 </math>

:* <math> kgV (5 , 7) = 35 </math>

:* <math> kgV (10 , 20) = 20 </math>

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:
: <math> a \cdot b \ = \ ggT (a ,b) \cdot kgV (a , b) </math>

; Beweis: 
:  Primfaktorzerlegung folgt. 

==Division mit Rest==

Sind ganze Zahlen <math> a </math> und <math> b </math> mit <math> b \ne 0 </math> gegeben, so gibt es eindeutig bestimmte ganze Zahlen <math> q </math> und <math> r </math> mit <math> a = q \cdot b + r </math> und <math> 0 \le r < | b | </math>. 

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

Eindeutigkeit: Übung.

<math> q </math> heißt der ganzzahlige Quotient, <math> r </math> der Rest der ganz-zahligen Division von <math> a </math> durch <math> b </math>. Im folgenden wird <math> r </math> auch als <math> a \bmod b </math> geschrieben, also <math> r =  a\bmod b </math>.

Bemerkung: 
: Es gilt <math> ggT (a , b) \ = \ ggT (r , b) </math>.  Denn jeder gemeinsame Teiler von <math> a </math> und <math> b </math> teilt auch <math> r = a - q \cdot b </math>, und umgekehrt teilt jeder gemeinsame Teiler von <math> r </math> und <math> b </math> auch <math> a = q \cdot b + r </math>. 

Beispiele: 
* <math> 97 = 2 \cdot 33 + 31 </math> 
* <math> 43 = 2 \cdot 21 + 1 </math>

==Euklidischer Algorithmus==

Der moderne Euklidische Algorithmus wird mittels einer Division mit Rest ausgeführt. Er beginnt mit den Zahlen <math> a_0 </math> und <math> b 
_0 </math> deren größter gemeinsamer Teiler bestimmt wird. Also : 
: <math> a_0 = q_0 \cdot b_0 + r_0 </math>, wie bei der Division mit Rest eingeführt, jedoch um einen Index ergänzt. Mit der Festlegung <math> a_i = b_{i-1} \ , \ b_i = r_{i-1} \ , \  q_i = a_i : b_i </math> und <math> r_i = a_i \bmod b_i </math> ergibt sich bis zum Abbruchkriterium <math> r_i = 0 </math> folgende Darstellung: 
: <math> a_1 = q_1 \cdot b_1 + r_1 </math>
: <math> a_2 = q_2 \cdot b_2 + r_2 </math>
:: <math> \vdots </math>
: <math> a_i = q_i \cdot b_i + r_i </math>

: Der Divisor <math> b_i </math> ist dann der größte gemeinsame Teiler <math> \operatorname{ggT} (a , b ) = b_i </math>.

Beispiele:  
: Der größte gemeinsame Teiler von <math> 1843 </math> und <math> 855 </math> wird mit Euklidischen Algorithmus berechnet :
: <math> 1843 = 2 \cdot 855 + 133 </math>
: <math> 855 = 6 \cdot 133 + 57 </math>
: <math> 133 = 2 \cdot 57 + 19 </math>
: <math> 57 = 3 \cdot 19 + 0 </math>
: Also ist <math> 19 </math> der größte gemeinsame Teiler von <math> 1843 </math> und <math> 855 </math>. 

: Der größte gemeinsame Teiler von <math> 1055 </math> und <math> 1028 </math> wird wie folgt berechnet : 
: <math> 1055 = 1 \cdot 1028 + 27 </math> 
: <math> 1028 = 38  \cdot 27 + 2 </math> 
: <math> 27 = 13 \cdot 2 + 1 </math>
: <math> 2 = 2 \cdot 1 + 0 </math>
: Demnach sind <math> 1055 </math> und <math> 1028 </math> teilerfremd, bzw. haben keinen größten gemeinsamen Teiler.

==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 [[wikipedia:de:Erweiterter_Euklidischer_Algorithmus|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==

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

<div style="padding: 2em 0em 0em 0em">
<!--:&rarr;&nbsp;&nbsp;[[Mathematik: Zahlentheorie: Größter gemeinsamer Teiler|nächstes Kapitel]]-->
:&rarr;&nbsp;&nbsp;[[Mathematik: Zahlentheorie: Fundamentalsatz der Arithmetik|voriges Kapitel]]
:&rarr;&nbsp;&nbsp;[[Mathematik: Zahlentheorie|Zurück zum Inhaltsverzeichnis "Zahlentheorie"]]
:&rarr;&nbsp;&nbsp;[[Mathematik: Inhaltsübersicht|Zur Inhaltsübersicht]]
</div>
<math></math>