Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 20

Aus Wikiversity

Wir kehren zur Thematik der Primzahlen und der Primfaktorzerlegung einer natürlichen Zahl zurück. Bisher kennen wir nur die Existenz einer Primfaktorzerlegung (siehe Satz 12.9), aber noch nicht die Eindeutigkeit. Obwohl wir diese Fragestellung für natürliche Zahlen formuliert haben, ergibt sich im Kontext der ganzen Zahlen ein neuer Zusammenhang, der für diese Thematik hilfreich ist.



Teilerfremdheit und das Lemma von Bezout

Aufgabe

Die Wasserspedition „Alles im Eimer“ verfügt über einen - und einen -Liter-Eimer, die allerdings keine Markierungen haben. Sie erhält den Auftrag, insgesamt genau einen Liter Wasser von der Nordsee in die Ostsee zu transportieren. Kann sie diesen Auftrag erfüllen?


Die Aufgabe ist lösbar: Man macht dreimal den -Liter-Eimer in der Nordsee voll und transportiert dies in die Ostsee. Danach (oder gleichzeitig) macht man zweimal den -Liter-Eimer in der Ostsee voll und transportiert dies in die Nordsee. Unterm Strich hat man dann

Liter transportiert (eine andere Möglichkeit ist ). Die dieser Überlegung zugrunde liegende Aussage heißt Lemma von Bezout.


Satz  

Es seien zwei teilerfremde natürliche Zahlen.

Dann gibt es ganze Zahlen mit .

Beweis  

Wir beweisen die Aussage durch Induktion über das Maximum von und , wobei wir ohne Einschränkung wählen können. Wenn das Maximum ist, so sind beide Zahlen und somit nicht teilerfremd. Wenn das Maximum ist, so ist und somit ergeben und eine Darstellung der . Es seien nun teilerfremd, und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als sind, schon bewiesen. Dann ist , da bei die beiden Zahlen nicht teilerfremd sind. Ebenso können wir ausschließen. Wir betrachten das Zahlenpaar und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als . Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch und teilerfemd sind. Dazu führen wir einen Widerspruchsbeweis.  Nehmen wir also an, dass und nicht teilerfremd sind. Dann gibt es eine natürliche Zahl , die sowohl als auch teilt. Dies bedeutet wiederum, dass es natürliche Zahlen mit und gibt. Doch dann ist

ebenfalls ein Vielfaches von , im Widerspruch zur Teilerfremdheit von und .  Die Induktionsvoraussetzung ist also auf und anwendbar und somit gibt es ganze Zahlen mit

Dann ist aber auch

und wir haben eine Darstellung der mit und gefunden.


Man sagt auch, dass eine Darstellung der als eine Linearkombination der und ist. Die heißen Koeffizienten der Darstellung.

Die Untergruppen von

Die Division mit Rest, die wir bisher nur für natürliche Zahlen formuliert haben, überträgt sich unmittelbar auf ganze Zahlen (der Divisor bleibt eine natürliche Zahl).


Satz

Es sei eine fixierte positive natürliche Zahl.

Dann gibt es zu jeder ganzen Zahl eine eindeutig bestimmte ganze Zahl und eine eindeutig bestimmte natürliche Zahl , , mit

Beweis

Siehe Aufgabe 20.9.



Definition  

Es sei eine Gruppe. Eine Teilmenge heißt Untergruppe von wenn folgendes gilt.

  1. .
  2. Mit ist auch .
  3. Mit ist auch .

In einer Untergruppe kann man also die Verknüpfung der Gruppe ausführen, man kann das Inverse nehmen und das neutrale Element gehört dazu. In additiver Schreibweise, die für uns im Mittelpunkt steht, bedeuten die Bedingungen einfach

  1. .
  2. Mit ist auch .
  3. Mit ist auch das Negative .

Beispielsweise bilden alle Vielfachen der innerhalb der ganzen Zahlen eine Untergruppe, die wir mit bezeichnen. Es ist ja

wenn und sind, so ist

nach dem Distributivgesetz und mit ist . Wie im eingangs gegebenen Beispiel kann man sich eine Menge von ganzen Zahlen (Eimergrößen) vorgeben und sich fragen, welche Zahlen man daraus mit Hilfe von ganzzahligen Koeffizienten bilden kann (welche Wassermengen man transportieren kann). Es geht also um die Menge aller Zahlen der Form

Diese Gesamtmenge bildet eine Untergruppe von , siehe Aufgabe 20.27, man spricht von der von den erzeugten Untergruppe von . Statt Eimern kann man sich auch eine Menge von ganzzahligen Pfeilen, die man hintereinanderlegen und umdrehen kann, vorstellen, oder eine vorgegebene Menge an Sprungmöglichkeiten, oder eine Menge an Gewichten. Der folgende Satz heißt auch „Ein-Eimer-Satz“.



Satz  

Die Untergruppen von sind genau

die Teilmengen der Form

mit einer eindeutig bestimmten nichtnegativen Zahl .

Beweis  

Eine Teilmenge der Form ist aufgrund der Distributivgesetze eine Untergruppe. Es sei umgekehrt eine Untergruppe. Bei kann man nehmen, so dass wir voraussetzen dürfen, dass neben noch mindestens ein weiteres Element enthält. Wenn negativ ist, so muss die Untergruppe auch das Negative davon, also enthalten, welches positiv ist. D.h. enthält auch positive Zahlen. Es sei nun die kleinste positive Zahl aus . Wir behaupten . Dabei ist die Inklusion klar, da mit alle (positiven und negativen) Vielfachen von dazugehören müssen. Für die umgekehrte Inklusion sei beliebig. Nach der Division mit Rest gilt

Wegen und ist auch . Nach der Wahl von muss wegen gelten: Dies bedeutet und damit , also .



Lemma  

Es seien ganze Zahlen und die davon erzeugte Untergruppe.

Eine ganze Zahl ist ein gemeinsamer Teiler der genau dann, wenn ist, und ist ein größter gemeinsamer Teiler genau dann, wenn ist.

Beweis  

Aus folgt sofort für jedes , was gerade bedeutet, dass diese Zahlen teilt, also ein gemeinsamer Teiler ist. Es sei umgekehrt ein gemeinsamer Teiler. Dann ist und da die kleinste Untergruppe ist, die alle enthält, muss gelten.

Aufgrund von Satz 20.4 wissen wir, dass es eine ganze Zahl gibt mit . Für einen anderen gemeinsamen Teiler der gilt , so dass von allen anderen gemeinsamen Teilern geteilt wird, also ein größter gemeinsamer Teiler ist.




Der Euklidische Algorithmus

Der euklidische Algorithmus dient dazu, zu gegebenen Zahlen ihren größten gemeinsamen Teiler zu bestimmen, und eine Darstellung dieses größten gemeinsamen Teilers ale eine Linearkombination der und explizit zu finden.

Es seien ganze Zahlen, . Dann kann man die Division mit Rest durchführen und erhält mit . Danach kann man (bei ) die Division mit Rest von durch durchführen, d.h. nimmt die Rolle von und die Rolle von ein und erhält einen neuen Rest. Dies kann man fortsetzen, und da dabei die Reste immer kleiner werden bricht das Verfahren irgendwann ab.



Definition  

Es seien zwei ganze Zahlen (mit ) gegeben. Dann nennt man die durch die Anfangsbedingungen und und die mittels der Division mit Rest

rekursiv bestimmte Folge die Folge der euklidischen Reste.



Satz  

Es seien ganze Zahlen und gegeben.

Dann besitzt die Folge , , der euklidischen Reste folgende Eigenschaften.

  1. Es ist oder .[1]
  2. Es gibt ein (minimales) mit .
  3. Es ist

    für alle

  4. Sei der erste Index derart, dass ist. Dann ist

Beweis  

  1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
  2. Solange ist, wird die Folge der natürlichen Zahlen immer kleiner, so dass irgendwann der Fall eintreten muss.
  3. Wenn ein gemeinsamer Teiler von und von ist, so zeigt die Beziehung

    dass auch ein Teiler von und damit ein gemeinsamer Teiler von und von ist. Die Umkehrung folgt genauso.

  4. Dies folgt aus (3) mit der Gleichungskette


Beispiel

Aufgabe

Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .


Lösung


Der Euklidische Algorithmus liefert:

Die Zahlen und sind also teilerfremd.


Bei kleinen Zahlen sieht man häufig relativ schnell direkt, was ihr größter gemeinsamer Teiler ist, da man die Primfaktorzerlegung kennt bzw. mögliche gemeinsame Teiler schnell übersehen kann. Bei zwei größeren Zahlen müssten aber viel zu viele Probedivisionen durchgeführt werden! Der euklidische Algorithmus ist also zur Bestimmung des größten gemeinsamen Teilers ein sehr effektives Verfahren!

Wenn man mit dem euklidischen Algorithmus den größten gemeinsamen Teiler von zwei Zahlen und gefunden hat, so kann man aus diesen Rechnungen auch die Quotienten und bestimmen, da dann alle euklidischen Reste Vielfache von sind.



Darstellung des größten gemeinsamen Teilers

Mit dem euklidischen Algorithmus kann man auch durch Zurückrechnen eine Darstellung des größten gemeinsamen Teilers als Linearkombination der beiden vorgegebenen Zahlen erhalten. Dazu seien

die Gleichungen im euklidischen Algorithmus und . Aus der letzten Gleichung

erhält man die Darstellung

von als Linearkombination mit und . Mit der vorhergehenden Zeile

bzw.

kann man in dieser Darstellung ersetzen und erhält eine Darstellung von als Linearkombination von und . So fortfahrend erhält man schließlich eine Darstellung von

als Linearkombination von und .


Beispiel  

Wir wollen für und eine Darstellung des größten gemeinsamen Teilers finden. Wir führen dazu den euklidischen Algorithmus durch.

D.h. ist der größte gemeinsame Teiler von und . Rückwärts gelesen erhält man daraus die Darstellung




Kommensurabilität

Es seien zwei Strecken und gegeben. Man sagt, dass ein (ganzzahliges) Vielfaches von ist, wenn es eine natürliche Zahl mit der Eigenschaft gibt, dass sich die Strecke ergibt, wenn man die Strecke -fach gerade hintereinanderlegt (die Strecke wird also -mal genommen). Für zwei Strecken und gibt es das folgende Konzept, das ihre ganzzahlige Vergleichbarkeit ausdrückt. Man beachte, dass dieses Konzept unabhängig von solchen Messungen ist, die die Längen in Zahlen mit Hilfe von Einheiten ausdrücken. Es werden nur die beiden Längen gegeneinander gemessen, man verwendet keine normierten Standardlängen.


Definition  

Zwei Strecken und heißen kommensurabel, wenn es eine Strecke mit der Eigenschaft gibt, dass beide Strecken ganzzahlige Vielfache von sind.

Auch vom euklidischen Algorithmus gibt es in diesem Kontext eine sinnvolle Version. Die Strecke sei mindestens so lang wie . Dann ist

mit und einer „Reststrecke“ , die kürzer als ist und eventuell ist. Die Gleichung ist dabei als eine Gleichung von hintereinander hingelegten Strecken zu verstehen. Wie in Satz 20.7 ergibt sich, dass mit und auch und kommensurabel sind. Wenn man dieses Verfahren rekursiv fortsetzt, so tritt im Falle der Kommensurabilität irgendwann die Situation auf, wo die kleine Strecke in die größere Strecke voll aufgeht. Somit hat man dann auch die größte gemeinsame Teilerstrecke gefunden.


<< | Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)


  1. Für . Da auch negativ sein könnte ist dies bei als zu lesen.