Kurs:Elemente der Algebra (Osnabrück 2024-2025)/Vorlesung 16
- Der Chinesische Restsatz für
Satz
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
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 Fakt ***** 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 .
Korollar
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 .
Beweis
Dies folgt aus dem chinesischen Restsatz und Fakt *****.
- Die Eulersche -Funktion
Satz
Genau dann ist eine Einheit modulo (d.h. repräsentiert eine Einheit in ), wenn und teilerfremd sind.
Beweis
Beweisvariante
Sind und teilerfremd, so gibt es nach Fakt ***** 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 Fakt ***** an, wie viele Zahlen , , zu teilerfremd sind.
Für eine Primzahl ist . Eine Verallgemeinerung des kleinen Fermat ist der folgende Satz von Euler.
Satz
Es 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
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
Es sei eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
(die seien also verschieden und ).
Dann ist
Beweis
<< | Kurs:Elemente der Algebra (Osnabrück 2024-2025) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF) |
---|