Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 8

Aus Wikiversity
Als Alternative wurde über ein Vorlesungslama ...


In dieser Vorlesung besprechen wir die Teilbarkeitsrelation innerhalb der natürlichen und der ganzen Zahlen genauer. Dies ist einerseits eine wichtige Ordnungsrelation, die darüber hinaus eng mit der additiven und der multiplikativen Struktur der ganzen Zahlen verbunden ist. Insbesondere werden wir die Untergruppen der ganzen Zahlen charakterisieren, was wiederum eine wichtige Voraussetzung für die Konstruktion von endlichen Ringen und Körpern in der zwölften Vorlesung ist, und wir werden die Eindeutigkeit der Primfaktorzerlegung in beweisen. Ferner führen die Überlegungen zum euklidischen Algorithmus.



Das Lemma von Bezout

Beispiel  

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

Dies wird sich weiter unten als Korollar zu

Korollar 8.5 ergeben, man kann es aber auch direkt durch Induktion über das Maximum von und beweisen, siehe

Aufgabe 8.7.


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 für ganze Zahlen ist analog zur Polynomdivision.


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 8.8.


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 8.37, 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 .



Korollar

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

Siehe Aufgabe 8.15.


Dies besagt insbesondere, dass es stets einen größten gemeinsamen Teiler gibt. Im teilerfremden Fall bedeutet es, dass es eine Darstellung der als ganzzahlige Linearkombination der gibt.



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!



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




Kleinstes gemeinsames Vielfaches und größter gemeinsamer Teiler

Zu einer ganzen Zahl besteht aus allen Vielfachen von . Zu zwei Zahlen besteht somit der Durchschnitt aus allen Zahlen, die sowohl von als auch von Vielfache sind, also aus allen gemeinsamen Vielfachen von und . In der Tat gilt die folgende Aussage.



Lemma

Es seien ganze Zahlen.

Dann ist

wobei das kleinste gemeinsame Vielfache der ist.

Beweis

Siehe Aufgabe 8.27.


Für ganze Zahlen setzen wird den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache stets positiv an, um Eindeutigkeit zu erzielen. Grundsätzlich hat jeweils das Negative dazu die gleichen Eigenschaften.


Lemma

Für natürliche Zahlen gelten folgende Aussagen.

  1. Für teilerfremde ist
  2. Es gibt mit

    wobei teilerfremd sind.

  3. Es ist
  4. Es ist

Beweis

Siehe Aufgabe 8.28.


Der Teil (4) der vorstehenden Aussage erlaubt es, das kleinste gemeinsame Vielfache zu zwei Zahlen algorithmisch dadurch zu bestimmen, dass man ihren größten gemeinsamen Teiler mit Hilfe des euklidischen Algorithmus bestimmt und das Produkt durch diesen teilt.



Der Hauptsatz der elementaren Zahlentheorie

Wir möchten nun zur Primfaktorzerlegung, deren Existenz wir bereits in Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024)) gezeigt haben, beweisen, dass sie eindeutig ist. Natürlich kann man

schreiben, mit eindeutig ist also eindeutig bis auf die Reihenfolge gemeint. Um dies zu zeigen brauchen wir zunächst das sogenannte Lemma von Euklid, das eine wichtige Eigenschaft einer Primzahl beschreibt.


Satz  

Es sei eine Primzahl und teile ein Produkt von natürlichen Zahlen .

Dann teilt einen der Faktoren.

Beweis  

Wir setzen voraus, dass kein Vielfaches von ist (andernfalls sind wir fertig). Dann müssen wir zeigen, dass ein Vielfaches von ist. Unter der gegebenen Voraussetzung sind und teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen mit

Da ein Vielfaches von ist, gibt es ein mit

Daher ist

Also ist ein Vielfaches von .


Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl ein beliebiges Produkt teilt, dann teilt mindestens einen Faktor. Man wendet das Lemma einfach auf an (formal ist das eine Induktion über die Anzahl der Faktoren). Dies wird im Beweis des folgenden Hauptsatzes der elementaren Zahlentheorie verwendet.


Satz  

Jede natürliche Zahl , , besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

mit Primzahlen , und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

Beweis  

Die Existenz der Primfaktorzerlegung wurde bereits in Satz 2.6 (Mathematik für Anwender (Osnabrück 2023-2024)) gezeigt. Die Eindeutigkeit wird durch Induktion über gezeigt. Für liegt eine Primzahl vor. Sei nun und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl das Produkt rechts teilt. Nach Satz 6.12 muss dann einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass von geteilt wird. Da selbst eine Primzahl ist, folgt, dass sein muss. Daraus ergibt sich durch Kürzen, dass

ist. Nennen wir diese Zahl . Da ist, können wir die Induktionsvoraussetzung auf anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen. 

In der kanonischen Primfaktorzerlegung schreibt man die beteiligten Primzahlen in aufsteigender Reihenfolge mit ihrem jeweiligen Exponenten, also beispielsweise


<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)

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