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

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 .



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.



Es sei eine Primzahl und eine Potenz davon.

Dann 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)