Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 15

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Der Hauptsatz der elementaren Zahlentheorie

Wir beweisen nun, dass sich jede natürliche Zahl in eindeutiger Weise als Produkt von Primzahlen darstellen lässt.



Satz  

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

Dann teilt einen der Faktoren.

Beweis  

Die Voraussetzung bedeutet, dass

in ist. Da eine Primzahl ist, ist dieser Restklassenring nach Satz 14.13 ein Körper, so dass ein Faktor null sein muss. Sagen wir . Dies bedeutet aber zurückübersetzt nach , dass ein Vielfaches von ist.




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  

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.



Lemma  

Es seien und positive natürliche Zahlen. Dann wird von genau dann geteilt,

wenn für jede Primzahl die Beziehung

gilt.

Beweis  

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




Korollar  

Es seien und positive natürliche Zahlen mit den Primfaktorzerlegungen und .

Dann ist

und

Beweis  

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.


Definition  

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.


Definition  

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 .



Lemma  

Es sei ein Produkt aus kommutativen Ringen.

Dann gilt für die Einheitengruppe von die Beziehung

Beweis  

Dies ist klar, da ein Element genau dann eine Einheit ist, wenn es in jeder Komponente eine Einheit ist.




Der Chinesische Restsatz für



Satz

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

Da die Ringe links und rechts beide endlich sind und die gleiche Anzahl von Elementen haben, nämlich , genügt es, die Injektivität zu zeigen. Sei eine natürliche Zahl, die im Produktring (rechts) zu null wird, also modulo den Rest null hat für alle . Dann ist ein Vielfaches von für alle , d.h., es ist ein gemeinsames Vielfaches dieser Potenzen. Daraus folgt aufgrund von

Lemma 4.8,

dass ein Vielfaches des Produktes sein muss, also ein Vielfaches von . Damit ist in und die Abbildung ist injektiv.


Beispiel

Aufgabe

(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


Lösung

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




Korollar  

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 .

Beweis  

Dies folgt aus dem chinesischen Restsatz und Lemma 15.7.




Die Eulersche -Funktion



Satz  

Genau dann ist eine Einheit modulo (d.h. repräsentiert eine Einheit in ), wenn und teilerfremd sind.

Beweis  

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, so dass also

gilt. Dann ist aber wieder und und sind teilerfremd.




Definition  

Zu einer natürlichen Zahl bezeichnet die Anzahl der Elemente von . Man nennt die Eulersche Funktion.

Bemerkung  

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.



Satz  

Sei eine natürliche Zahl.

Dann gilt für jede zu teilerfremde Zahl die Beziehung

Beweis  

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.



Lemma  

Es sei eine Primzahl und eine Potenz davon.

Dann ist

Beweis  

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 .




Korollar  

Sei eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung

(die seien also verschieden und ).

Dann ist

Beweis  

Die erste Gleichung folgt aus Korollar 15.10 und die zweite aus Lemma 15.15.



<< | Kurs:Einführung in die Algebra (Osnabrück 2009) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)