Kurs:Elemente der Algebra (Osnabrück 2024-2025)/Vorlesung 16
- 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.
Dies folgt unmittelbar aus Satz 15.7.
Beweisvariante
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. Es sei eine natürliche Zahl, die im Produktring (rechts) zu wird, also modulo den Rest hat für alle . Dann ist ein Vielfaches von für alle , d.h. in der Primfaktorzerlegung von muss zumindest mit dem Exponenten vorkommen. Also muss nach Lemma 9.9 ein Vielfaches des Produktes sein, also ein Vielfaches von . Damit ist in und die Abbildung ist injektiv.
Unter den Basislösungen zu einer simultanen Kongruenz versteht man die kleinsten natürlichen Zahlen, die modulo den vorgegebenen Zahlen ein Restetupel ergeben, das an genau einer Stelle den Wert und sonst überall den Wert besitzt. Aus diesen Basislösungen kann man die Lösungen zu sämtlichen simultanen Kongruenzen berechnen.
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.6.
- Die Eulersche -Funktion
Genau dann ist eine Einheit modulo (d.h. repräsentiert eine Einheit in ), wenn und teilerfremd sind.
Dies folgt aus Lemma 14.9.
Beweisvariante
Sind und teilerfremd, so gibt es nach Satz 8.5 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 16.4 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 16.3 und die zweite aus Lemma 16.8.
<< | Kurs:Elemente der Algebra (Osnabrück 2024-2025) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF) |
---|