Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 15
- Der Hauptsatz der elementaren Zahlentheorie
Wir beweisen nun, dass sich jede natürliche Zahl in eindeutiger Weise als Produkt von Primzahlen darstellen lässt.
Es sei eine Primzahl und teile ein Produkt von natürlichen Zahlen .
Dann teilt einen der Faktoren.
Die Voraussetzung bedeutet, dass
in ist. Da eine Primzahl ist, ist dieser Restklassenring nach Satz 14.13 ein Körper, sodass ein Faktor null sein muss. Sagen wir . Dies bedeutet aber zurückübersetzt nach , dass ein Vielfaches von ist.
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.
Wir beweisen die Existenz und die Eindeutigkeit jeweils durch Induktion. Für liegt eine Primzahl vor. Bei ist entweder eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung mit kleineren Zahlen . Für diese Zahlen gibt es nach der Induktionsvoraussetzung eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für zusammen. Zur Eindeutigkeit: Bei ist die Aussage klar. Im Allgemeinen seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir
Insbesondere teilt die Primzahl dann das Produkt rechts, und damit nach dem Lemma von Euklid einen der Faktoren. Nach Umordnung können wir annehmen, dass von geteilt wird. Da selbst eine Primzahl ist, folgt, dass sein muss. Da nullteilerfrei ist, kann man beidseitig durch dividieren und erhält die Gleichung
Da ist, können wir die Induktionsvoraussetzung der Eindeutigkeit auf anwenden.
Zu einer Primzahl und einer positiven ganzen Zahl ist der Exponent, also die Vielfachheit, mit der als Primfaktor in auftritt, eindeutich festgelegt. Dieser Exponent wird mit bezeichnet. Die eindeutige Primfaktorzerlegung kann man auch als
schreiben, wobei das Produkt in Wirklichkeit endlich ist, da in der Primfaktorzerlegung nur endlich viele Primfaktoren mit einem positiven Exponenten vorkommen.
Es seien und positive natürliche Zahlen. Dann wird von genau dann geteilt,
wenn für jede Primzahl die Beziehung
gilt.
. Aus der Beziehung
folgt
in Verbindung mit der eindeutigen Primfaktorzerlegung,
dass die Primfaktoren von mit mindestens ihrer Vielfachheit auch in vorkommen müssen.
. Wenn die Exponentenbedingung erfüllt ist, so ist
eine natürliche Zahl mit
.
Es seien und positive natürliche Zahlen mit den Primfaktorzerlegungen und .
Dann ist
und
Dies folgt direkt aus Lemma 15.3.
- Produktringe
Um die Restklassenringe von besser verstehen zu können, insbesondere dann, wenn man als Produkt von kleineren Zahlen schreiben kann - z.B., wenn die Primfaktorzerlegung bekannt ist -, braucht man den Begriff des Produktringes.
Es seien kommutative Ringe. Dann heißt das Produkt
versehen mit komponentenweiser Addition und Multiplikation, der Produktring der , .
Eng verwandt mit dem Begriff des Produktringes ist das Konzept der idempotenten Elemente.
Ein Element eines kommutativen Ringes heißt idempotent, wenn gilt.
Die Elemente und sind trivialerweise idempotent, man nennt sie die trivialen idempotenten Elemente. In einem Produktring sind auch diejenigen Elemente, die in allen Komponenten nur den Wert oder besitzen, idempotent, also bspw. . In einem Integritätsbereich gibt es nur die beiden trivialen idempotenten Elemente: Ein idempotentes Element besitzt die Eigenschaft
Im nullteilerfreien Fall folgt daraus oder .
Dies ist klar, da ein Element genau dann eine Einheit ist, wenn es in jeder Komponente eine Einheit ist.
- Der Chinesische Restsatz für
Es sei eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
(die seien also verschieden und ).
Dann induzieren die kanonischen Ringhomomorphismen einen Ringisomorphismus
Zu gegebenen ganzen Zahlen gibt es also genau eine natürliche Zahl , die die simultanen Kongruenzen
löst.
Beweis
Beispiel
(a) Bestimme für die Zahlen , und modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
die Restetupel und repräsentieren.
(b) Finde mit den Basislösungen die kleinste positive Lösung der simultanen Kongruenzen
(a) : Alle Vielfachen von haben modulo und modulo den Rest . Unter diesen Vielfachen muss also die Lösung liegen. hat modulo den Rest , somit hat modulo den Rest . Also repräsentiert das Restetupel .
: Hier betrachtet man die Vielfachen von , und hat modulo den Rest . Also repräsentiert das Restetupel .
: Hier betrachtet man die Vielfachen von , und hat modulo den Rest . Also repräsentiert das Restetupel .
(b) Man schreibt (in )
Die Lösung ist dann
Die minimale Lösung ist dann .
Es sei eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung (die seien also verschieden und ).
Dann gibt es einen kanonischen Gruppenisomorphismus
Insbesondere ist eine Zahl genau dann eine Einheit modulo , wenn sie eine Einheit modulo ist für .
Dies folgt aus dem chinesischen Restsatz und Lemma 15.7.
- Die Eulersche -Funktion
Genau dann ist eine Einheit modulo (d.h. repräsentiert eine Einheit in ), wenn und teilerfremd sind.
Sind und teilerfremd, so gibt es nach Satz 4.1 eine Darstellung der , es gibt also ganze Zahlen mit
Betrachtet man diese Gleichung modulo , so ergibt sich in . Damit ist eine Einheit mit Inversem .
Ist umgekehrt eine Einheit in , so gibt es ein mit in . Das bedeutet aber, dass ein Vielfaches von ist, sodass also
gilt. Dann ist aber wieder und und sind teilerfremd.
Zu einer natürlichen Zahl bezeichnet die Anzahl der Elemente von . Man nennt die Eulersche Funktion.
Die Eulersche Funktion gibt also für nach Satz 15.11 an, wie viele Zahlen , , zu teilerfremd sind.
Für eine Primzahl ist . Eine Verallgemeinerung des kleinen Fermat ist der folgende Satz von Euler.
Es sei eine natürliche Zahl.
Dann gilt für jede zu teilerfremde Zahl die Beziehung
Das Element gehört zur Einheitengruppe , die Elemente besitzt. Nach dem Satz von Lagrange ist aber die Gruppenordnung ein Vielfaches der Ordnung des Elementes.
Wir geben abschließend Formeln an, wie man die Eulersche -Funktion berechnet, wenn die Primfaktorzerlegung bekannt ist.
Eine Zahl ist genau dann teilerfremd zu einer Primzahlpotenz , wenn sie teilerfremd zu selbst ist, und dies ist genau dann der Fall, wenn sie kein Vielfaches von ist. Unter den natürlichen Zahlen sind genau die Zahlen
Vielfache von . Das sind Stück, und daher gibt es
Einheiten in . Also ist .
Es sei eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
(die seien also verschieden und ).
Dann ist
Die erste Gleichung folgt aus Korollar 15.10 und die zweite aus Lemma 15.15.