Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 3/kontrolle

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Der euklidische Algorithmus

Euklidische Bereiche heißen so, weil in ihnen der euklidische Algorithmus ausgeführt werden kann.


Definition  Referenznummer erstellen

Seien Elemente (mit ) eines euklidischen Bereichs mit euklidischer Funktion gegeben. Dann nennt man die durch die Anfangsbedingungen und und die mittels der Division mit Rest

rekursiv bestimmte Folge die Folge der euklidischen Reste.[1]



Satz  Referenznummer erstellen

Seien zwei Elemente eines euklidischen Bereiches mit euklidischer Funktion gegeben. Dann besitzt die Folge , , der euklidischen Reste folgende Eigenschaften.

  1. Es ist .
  2. Es gibt ein (minimales) mit .
  3. Es ist
  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


Als Beispiel zum Euklidischen Algorithmus lösen wir die folgende Aufgabe.


Aufgabe

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


Lösung

Der größte gemeinsame Teiler von 1071 und 1029 wird mit dem Euklidischen Algorithmus wie folgt berechnet:

Der größte gemeinsame Teiler von 1071 und 1029 ist somit 21.



Aufgabe

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


Lösung

Wir setzen und und führen die Division mit Rest durch. Es ist (in oder in )

Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist , so dass die Division mit Rest ergibt:

Die nächste durchzuführende Division ist somit

Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist , so dass die Division mit Rest ergibt:

Da dies eine Einheit ist, sind und teilerfremd.





Das Lemma von Bezout und das Lemma von Euklid



Satz  Satz 3.3 ändern

Sei ein Hauptidealring. Dann gilt:

Elemente besitzen stets einen größten gemeinsamen Teiler , und dieser lässt sich als Linearkombination der darstellen, d.h. es gibt Elemente mit .

Insbesondere besitzen teilerfremde Elemente eine Darstellung der .

Beweis  

Sei das von den Elementen erzeugte Ideal. Da wir in einem Hauptidealring sind, handelt es sich um ein Hauptideal; es gibt also ein Element mit . Wir behaupten, dass ein größter gemeinsamer Teiler der ist. Die Inklusionen zeigen, dass es sich um einen gemeinsamen Teiler handelt. Sei ein weiterer gemeinsamer Teiler der . Dann ist wieder , was wiederum bedeutet. Die Darstellungsaussage folgt unmittelbar aus .

Im teilerfremden Fall ist .


Die vorstehende Aussage heißt Lemma von Bezout. In einem euklidischen Bereich kann man mit dem euklidischen Algorithmus eine Darstellung des größten gemeinsamen Teilers bestimmen, indem man rückwärts durch den Algorithmus wandert. Die folgende Aussage heißt Lemma von Euklid.



Lemma  Lemma 3.4 ändern

Sei ein Hauptidealbereich und . Es seien und teilerfremd und teile das Produkt . Dann teilt den Faktor .

Beweis  

Da und teilerfremd sind, gibt es nach dem Lemma von Bezout Elemente mit . Die Voraussetzung, dass das Produkt teilt, schreiben wir als . Damit gilt

was zeigt, dass ein Vielfaches von ist.




Die Faktorialität von Hauptidealbereichen



Satz  Satz 3.5 ändern

Sei ein Hauptidealbereich. Dann ist ein Element genau dann prim,

wenn es irreduzibel ist.

Beweis  

Ein Primelement in einem Integritätsbereich ist nach Lemma 1.16 stets irreduzibel. Sei also umgekehrt irreduzibel, und nehmen wir an, dass das Produkt teilt, sagen wir . Nehmen wir an, dass kein Vielfaches von ist. Dann sind aber und teilerfremd, da eine echte Inklusionskette der Irreduzibilität von widerspricht. Damit teilt nach dem Lemma von Euklid den anderen Faktor .




Lemma  Lemma 3.6 ändern

In einem Hauptidealbereich lässt sich jede Nichteinheit darstellen als Produkt von irreduziblen Elementen.

Beweis  

Angenommen, jede Zerlegung enthalte nicht irreduzible Elemente. Dann gibt es in jedem solchen Produkt einen Faktor, der ebenfalls keine Zerlegung in irreduzible Faktoren besitzt. Wir erhalten also eine unendliche Kette , wobei ein nicht-trivialer Teiler von ist. Somit haben wir eine echt aufsteigende Idealkette

Die Vereinigung dieser Ideale ist aber Aufgabe 3.14 ebenfalls ein Ideal und nach Voraussetzung ein Hauptideal. Dies ist ein Widerspruch.




Satz  Satz 3.7 ändern

In einem Hauptidealbereich lässt sich jede Nichteinheit darstellen als Produkt von Primelementen. Diese Darstellung ist eindeutig bis auf Reihenfolge und Assoziiertheit. Wählt man aus jeder Assoziiertheitsklasse von Primelementen einen festen Repräsentanten , so gibt es eine bis auf die Reihenfolge eindeutige Darstellung , wobei eine Einheit ist und die Repräsentanten sind.

Beweis  

Die erste Aussage folgt direkt aus Lemma 3.6 und Satz 3.5.

Die behauptete Eindeutigkeit bis auf Umordnung bedeutet, dass wenn

zwei Primfaktorzerlegungen sind, dass dann ist und es eine Permutation auf gibt derart, dass und assoziiert sind für alle . Wir beweisen diese Aussage durch Induktion über . Sei zuerst (das sei zugelassen). Dann steht links eine Einheit, also muss auch rechts eine Einheit stehen, was bedeutet.

Sei also und die Aussage sei für alle kleineren bewiesen. Die Gleichung bedeutet insbesondere, dass das Produkt rechts teilt. Da prim ist, muss nach dem Lemma von Euklid einen der Faktoren rechts teilen. Nach Umordnung kann man annehmen, dass von geteilt wird. Da ebenfalls prim ist, sind und assoziiert. Also ist

mit einer Einheit und man kann die Gleichung nach kürzen und erhält

Die Induktionsvoraussetzung liefert dann und dass jedes zu einem assoziiert ist.


Diesen Satz kann man auch so ausdrücken, dass Hauptidealbereiche faktoriell sind im Sinne der folgenden Definition. Für solche Bereiche gilt ganz allgemein, dass die Primfaktorzerlegung eindeutig ist.


Definition  Referenznummer erstellen

Ein Integritätsbereich heißt faktorieller Bereich, wenn die beiden folgenden Eigenschaften erfüllt sind.

  1. Jedes irreduzible Element in ist prim.
  2. Jedes Element , , ist ein Produkt aus irreduziblen Elementen.



Korollar  Referenznummer erstellen

Jede positive natürliche Zahl lässt sich eindeutig als Produkt von Primzahlen darstellen.

Beweis  

Dies folgt sofort aus Satz 3.7.




Korollar  Korollar 3.10 ändern

Sei ein Hauptidealbereich und seien und zwei Elemente mit Primfaktorzerlegungen

(wobei die Exponenten auch sein können und Einheiten sind). Dann gilt genau dann, wenn ist für alle Exponenten .

Beweis  

Wenn die Exponentenbedingung erfüllt ist, so ist und man kann

schreiben, was die Teilbarkeit bedeutet. Die Umkehrung folgt aus der Eindeutigkeit der Primfaktorzerlegung in Hauptidealbereichen (siehe Satz 3.7).



Beispiel  Referenznummer erstellen

Wir betrachten den Ring , der aus allen komplexen Zahlen der Form

besteht und ein Unterring des Ringes der Eisensteinzahlen ist. Letzterer Ring ist nach Satz 2.15 euklidisch und ein Hauptidealbereich. Dagegen gilt in noch nicht einmal die eindeutige Primfaktorzerlegung, es ist nämlich

und in beiden Zerlegungen sind die Faktoren irreduzibel, da es in (und im Eisensteinring) keine Elemente mit Betragsquadrat . Im Ring der Eisensteinzahlen sind wegen

die Faktoren zueinander assoziiert, aber nicht in , da es dort die Einheit nicht gibt. Das Ideal

ist in kein Hauptideal.




Restklassenringe von Hauptidealbereichen



Satz  Satz 3.12 ändern

Sei ein Hauptidealbereich und ein Element. Dann sind folgende Bedingungen äquivalent.

  1. ist ein Primelement.
  2. ist ein Integritätsbereich.
  3. ist ein Körper.

Beweis  

Die Äquivalenz (1) (2) gilt in jedem kommutativen Ring (auch für ), siehe Aufgabe *****, und (3) impliziert natürlich (2). Sei also (1) erfüllt und sei von verschieden. Wir bezeichnen einen Repräsentanten davon in ebenfalls mit . Es ist dann und es ergibt sich eine echte Idealinklusion . Ferner können wir schreiben, da wir in einem Hauptidealring sind. Es folgt . Da keine Einheit ist und prim (also nach Lemma 1.16 auch irreduzibel) ist, muss eine Einheit sein. Es ist also , und das bedeutet modulo , also in , dass eine Einheit ist. Also ist ein Körper.




Fußnoten
  1. Da wir einen euklidischen Bereich ohne Eindeutigkeitsbedingung in der Division mit Rest definiert haben, ist diese Restfolge nicht unbedingt eindeutig bestimmt. Die relevanten Eigenschaften hängen aber nicht von Auswahlen ab und in allen wichtigen Beispielen ist die Division mit Rest eindeutig.


<< | Kurs:Zahlentheorie (Osnabrück 2016-2017) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)