Vollständige und reduzierte Restsysteme
Aus obiger Tabelle ist keine einfache Formel zur allgemeinen Berechnung von φ(m) ersichtlich. Überraschenderweise gibt es eine derartige Formel. Sie beruht auf weitergehenden Eigenschaften der φ-Funktion. Um diese zu ergründen, betrachten wir die Reste modulo m noch etwas genauer. Wir definieren:
Definition (vollständiges und reduziertes Restsystem)
Sei m ≥ 1.
(a) | Eine Menge A ⊆ ℤ heißt ein (vollständiges) Restsystem modulo m, falls für alle r = 0, …, m − 1 genau ein a ∈ A existiert mit a ≡ r (m). |
(b) | Eine Menge B ⊆ ℤ heißt ein reduziertes Restsystem modulo m, falls für alle r = r1, …, rφ(m) genau ein b ∈ B existiert mit b ≡ r (m). |
Beispiele
(1) | Für m = 1 und a beliebig ist { a } ein vollständiges und zudem auch ein reduziertes Restsystem modulo 1. |
(2) | Sei m ≥ 1. Dann ist { 0, …, m − 1 } ein Restsystem und { r1, …, rφ(m) } ein reduziertes Restsystem modulo m. |
(3) | Modulo 10 ist { 4, 5, 6, …, 13 } ein Restsystem. Weiter sind { 1, 3, 7, 9 } und { 3, 9, 21, 27 } reduzierte Restsysteme, nicht aber { 2, 6, 14, 18 }. |
Wir sagen auch, dass Zahlen a1, …, ak ein (reduziertes) Restsystem modulo m bilden, wenn { a1, …, ak } ein solches System ist. Nützliche Äquivalenzen sind:
Satz (Äquivalenzen für Restsysteme)
Sei m ≥ 1. Dann gilt:
(a) | Zahlen a1, …, am bilden genau dann ein Restsystem modulo m, wenn sie paarweise inkongruent modulo m sind. |
(b) | Zahlen b1, …, bφ(m) bilden genau dann ein reduziertes Restsystem modulo m, wenn sie paarweise inkongruent und teilerfremd zu m sind. |
(c) | Ist A ein Restsystem modulo m, so ist B = { a ∈ A | (a, m) = 1 } ein reduziertes Restsystem modulo m. |
Der Beweis sei dem Leser zur Übung überlassen. Nützlich hierbei ist:
(+) Für alle m ≥ 1 und alle a, b gilt: a ≡ b (m) impliziert (a, m) = (b, m).
Kurz: Kongruentes Ersetzen ändert den ggT mit dem Modul nicht. Speziell bleibt die Teilerfremdheit von a und m erhalten, wenn wir a durch ein kongruentes b ersetzen.
Zusammenfassend halten wir folgende anschauliche Beschreibung fest:
Prinzip der Umordnung modulo m
Ein vollständiges Restsystem a1, …, am modulo m entsteht durch Permutation (Umordnung) der Zahlen 0, …, m − 1 modulo m:
Jede Zahl kann ihren Platz ändern und zudem durch eine modulo m kongruente Zahl ersetzt werden.
Analog geht ein reduziertes Restsystem aus den Resten r1, …, rφ(m) durch Umordnung und kongruente Ersetzung hervor.
Dieses Prinzip können wir visualisieren, indem wir kongruente Zahlen zeilenweise anordnen. Für den Modul m = 9 ergibt sich (mit rot = teilerfremd):
Ein vollständiges Restsystem modulo 9 erhalten wir, indem wir aus jeder Zeile genau ein Element auswählen (dargestellt durch grüne Kreise). Die natürliche (oder wie man in der Mathematik sagt „kanonische“) Wahl ist 0, …, 8, aber auch
9, −17, 2, 39, 40, −4, 6, 25, −10
ist möglich. Das kanonische reduzierte Restsystem modulo 9 ist
r1 = 1, r2 = 2, r3 = 4, r4 = 5, r5 = 7, r6 = rφ(9) = 8,
aber auch
−17, 2, 40, −4, 25, −10
ist ein reduziertes Restsystem. Allgemein erhalten wir aus einem beliebigen vollständigen Restsystem ein reduziertes System, indem wir alle Elemente streichen, die nicht zu teilerfremden Zeilen gehören. Dieses Vorgehen motiviert die Bezeichnung „reduziert“.
Skalierung von Restsystemen
Unser erstes Ergebnis ist, dass Restsysteme bei der Multiplikation mit einer zum Modul teilerfremden Zahl erhalten bleiben. Aus dieser Beobachtung wird sich später der Satz von Euler in wenigen Zeilen ergeben.
Satz (Umordnungssatz für Reste)
Sei m ≥ 1, und sei c teilerfremd zu m. Dann gilt:
(a) | { c0, c1, …, c(m − 1) } ist ein Restsystem modulo m. |
(b) | { cr1, cr2, …, crφ(m) } ist ein reduziertes Restsystem modulo m. |
Beweis
zu (a):
Die m Zahlen c 0, …, c (m − 1) sind nach der Kürzungsregel für Kongruenzen wegen (c, m) = 1 paarweise inkongruent modulo m. Damit bilden sie ein Restsystem modulo m.
zu (b):
Die φ(m) Zahlen c r1, … c rφ(m) sind nach der Kürzungsregel paarweise inkongruent und wegen (m, c) = 1 teilerfremd zu m. Damit bilden sie ein reduziertes Restsystem modulo m.
Definieren wir also f : { 0, …, m − 1 } → { 0, …, m − 1 } durch
f (a) = „das eindeutige r ∈ { 0, …, m − 1 } mit ca ≡ r (m)“ für alle a,
so ist f bijektiv, also eine Permutation der Zahlen 0, …, m − 1. Analoges gilt für die reduzierten Systeme.
Beispiele
(1) | Sei m = 10. Für c = 3 ergibt sich:
Für die teilerfremden Reste r1 = 1, r2 = 3, r3 = 7, r4 = 9 modulo 10 gilt:
|
(2) | Sei m = 12. Die folgende Tabelle listet alle Werte f (c1), …, f (c11) für c = 0, …, 11 (c senkrecht). Es ergeben sich genau dann vollständige Restsysteme (grüne Zeilen) modulo 12, wenn (c, 12) = 1. Reduzierte Systeme sind durch rote Kreise markiert. Wir multiplizieren die Zahlen 0, 1, …, 11 nacheinander mit c = 0, …, 11 und erhalten so modulo 12 rechnend die Zeilen der Tabelle. Eine Zeile ist genau dann ein Restsystem modulo 12, wenn c und 12 teilerfremd sind. |
Die Voraussetzung der Teilerfremdheit von c und m ist im Umordnungssatz wesentlich. Ist d = (c, m) ≥ 2 und k = m/d, so gilt
0 ≡ c 0 ≡ c k mod(m),
sodass { c0, c1, …, c(m − 1) } kein Restsystem modulo m ist.
Als allgemeines Motiv halten wir fest:
Teilerfremdheit ist eine gute Voraussetzung in der Zahlentheorie.
Dieses Motiv spielt auch für die folgende weitere Untersuchung der φ-Funktion eine Schlüsselrolle.