Z/nZ

In der Mathematik ist ein Restklassenring modulo einer positiven ganzen Zahl n eine Abstraktion der Klassifikation ganzer Zahlen hinsichtlich ihres Restes bei der Division durch n.

Dieser Artikel beschäftigt sich mit der algebraischen Definition und abstrakteren Eigenschaften von Restklassenringen. Für eine einfachere und verständlichere Einführung in die Rechenregeln siehe den Artikel Kongruenz (Zahlentheorie).

Definition

Ist $n\geq 2$ eine natürliche Zahl, dann werden ganze Zahlen mit gleichem Rest bei Division durch n zu sogenannten Restklassen modulo n zusammengefasst. Zwei ganze Zahlen sind also in derselben Restklasse, wenn ihre Differenz durch n teilbar ist. Die Restklassen bilden zusammen mit der unten erklärten Addition und Multiplikation den Restklassenring, der mit $\mathbb{Z}/n\mathbb{Z}$ oder $\mathbb Z/n$ oder $\mathbb{Z}_n$ bezeichnet wird (sprich „Z modulo n“).

Die Addition und Multiplikation von Restklassen erfolgt durch Addition und Multiplikation von beliebigen Elementen dieser Klassen (im Allgemeinen werden diese Elemente auch als Repräsentanten oder Vertreter bezeichnet) und anschließende Restbildung des Ergebnisses. Bezeichnet man die Restklasse von a mit [a], dann definiert man

$[a]+[b]:=[a + b] \text{ und }[a] \cdot[b]:=[a\cdot b]$

Dass diese Verknüpfungen des Restklassenrings wohldefiniert sind, liegt an der folgenden Eigenschaft der Restklassen.

Sind $a_1,\ b_1,\ a_2,\ b_2$ ganze Zahlen mit

[a₁] = [b₁] und [a₂] = [b₂],

dann gilt

$[a_1 + a_2] = [b_1 + b_2] \text{ sowie } [a_1 \cdot a_2] = [b_1 \cdot b_2]$ .

Die Verknüpfungen sind also unabhängig vom Repräsentanten der Restklasse definiert.

Schreibweisen und Konventionen

Die Schreibweise $\mathbb Z_n$ birgt Verwechslungsgefahr mit der Bezeichnung $\mathbb Z_p$ für den Ring der ganzen p-adischen Zahlen zu einer Primzahl p. Wird die Schreibweise $\mathbb Z_n$ für den Restklassenring favorisiert, so werden die p-adischen Zahlen mit $\mathbb Z_p^\land$ bezeichnet. Die Schreibweise $\Z/n\Z$ für die Restklassenringe ist umständlicher, aber eindeutiger. Die Schreibweise $\Z/n$ ist seltener und auch unglücklich wegen der Verwechslungsgefahr mit $\textstyle{{1\over n}\Z = \{{k\over n}\colon k\in\Z\}}$.

Um die lästige Schreibweise für die Äquivalenzklassen zu vermeiden, lässt man einfach die eckigen Klammern weg. Damit hat jede Äquivalenzklasse unendlich viele Namen; beispielsweise gelten mit der vereinbarten Schreibweise n = 0 und n − 1 = − 1 in $\Z/n\Z$. Legt man Wert auf einen eindeutigen Namen für die endlich vielen Elemente des Restklassenrings, so wählt man einen kanonischen Vertreter aus jeder Restklasse aus und identifiziert die Restklasse mit diesem:

Der Restklassenring $(\Z_n,+,\cdot)$ besteht nach dieser Konvention aus den Zahlen $0, 1,\ldots, n-1$. Durch die folgenden Kongruenzen

$(a + b) \mod n$ und

$(a\ \cdot\ b) \mod n$

im Ring $\Z$ der ganzen Zahlen erhalten wir Ergebnisse, die wir nach unserer Konvention nun sofort als Ergebnisse in $\Z_n$ interpretieren dürfen. Jede Kette arithmetischer Operationen in diesem Restklassenring (z. B. die Auswertung eines Polynoms $p\in\Z_n[X]$ an der Stelle X = k mit $k\in\Z_n$) kann als Auswertung in den ganzen Zahlen mit einer abschließenden Modulo-Reduktion stattfinden; es können aber auch an beliebigen (oder allen) Stellen bereits die Zwischenergebnisse einer modularen Reduktion unterzogen werden.

Ist die Zahl n = 2^k eine Zweierpotenz, so wird oft auch das um die Null symmetrisierte Vertretersystem $\textstyle{\{-{n\over 2},\ldots,-1,0,1,\ldots,{n\over 2}-1\}}$ gewählt. Dieses korrespondiert nämlich mit einer Binärdarstellung der Zahlen, bei der das höchstwertige Bit als Vorzeichen interpretiert wird.

Eigenschaften

Für jede natürliche Zahl $n \geq 2$ ist $\mathbb{Z}/n\mathbb{Z}$ ein kommutativer Ring mit Eins. Das Nullelement ist die Restklasse $n\mathbb{Z}$ und das Einselement die Restklasse $1 + n\mathbb{Z}$.

Ist p eine Primzahl, dann ist der Restklassenring $\mathbb{Z}/p\mathbb{Z}$ ein endlicher Körper, der Restklassenkörper modulo p, und wird mit $\mathbb F_p$ (von engl. "field" für Körper) bezeichnet. Inverse bezüglich der Multiplikation lassen sich dann eindeutig mittels des erweiterten euklidischen Algorithmus berechnen.

Ist dagegen n keine Primzahl, dann ist der Restklassenring modulo n kein Körper, da die Restklasse jedes echten Teilers von n ein Nullteiler ist, welcher kein Inverses bezüglich der Multiplikation besitzt.

Eine Restklasse $a+n\mathbb{Z}$ mit $\operatorname{ggT}(a, n) = 1$ heißt prime Restklasse modulo n. Die Gruppe der primen Restklassen modulo n heißt prime Restklassengruppe modulo n und wird mit $(\mathbb{Z}/n\mathbb{Z})^*$ symbolisiert. Sie ist die Einheitengruppe des Rings $\mathbb{Z}/n\mathbb{Z}$ und hat $\varphi(n)$ Elemente, wobei $\varphi$ die eulersche φ-Funktion ist.

Beispiele

Veranschaulichung am Zifferblatt der Uhr

Veranschaulichen kann man das Rechnen mit Restklassen anhand des Zifferblattes einer Analoguhr. Die Stunden sind von eins bis zwölf nummeriert, wobei Stunde 12 als Stunde 0 betrachtet wird.

Beginnt man bei Stunde 0 und addiert jeweils eine Stunde, erhält man der Reihe nach jede der zwölf Stunden des Zifferblattes. Man addiert zwei beliebige Stunden miteinander, indem man bei der ersten angegebenen Stunde beginnt und im Uhrzeigersinn die zweite Stundenangabe abzählt: Um 4 + 5 zu ermitteln, beginnt man bei Stunde 4 und zählt fünf Stunden weiter, man landet bei Stunde 9. Berechnet man nun 9 + 5, zählt also von Stunde 9 aus fünf Stunden weiter, landet man bei Stunde 2, es ist also 9 + 5 = 2 in diesem System. Wie kommt dieses Ergebnis zustande? Addiert man einfach die Stundenwerte, erhält man 14; und „14 Uhr“ stimmt auf dem zwölfstündigen Zifferblatt mit „2 Uhr“ überein, also ist hier 14 = 2. Das Ergebnis einer Addition ist also die normale Summe, eventuell abzüglich einer Zwölf. Dies entspricht dem Rest bei Division durch 12. Diese Art der Addition heißt „Addition modulo 12“. Man erkennt hier, dass die Addition der Zwölf eine Zahl nicht verändert, 12 + x = x für jede Stunde x. Das erklärt, warum die 12. Stunde hier als Stunde 0 bezeichnet wird.

Die Multiplikation wird auf die Addition zurückgeführt: Um beispielsweise $4 \cdot 3$ zu bestimmen, bildet man die Summe 3 + 3 + 3 + 3 und landet bei der 12. Stunde. Das Produkt $4 \cdot 4$ liefert „16 Uhr“, und das ist identisch mit „4 Uhr“; modulo 12 ist also $4 \cdot 4 = 4$.

Die zwölf Stundenwerte, zusammen mit den Regeln für Addition und Multiplikation, schreibt man als $(\mathbb{Z} / 12\mathbb{Z}, +, \cdot)$.

Was für zwölf geht, funktioniert auch für jede andere natürliche Zahl n. In $\mathbb{Z} / 4\mathbb{Z} = \{0, 1, 2, 3\}$ ist 1 = 1, 2 = 1 + 1, 3 = 1 + 1 + 1, 0 = 1 + 1 + 1 + 1.

Der Restklassenring modulo 2

Bei Division ganzer Zahlen durch 2 mit Rest ergibt sich als Rest entweder 0 oder 1. Damit ist $\Z / 2\Z = \Z_2 = \{0,1\}$ der kleinste aller Restklassenringe. Da 2 eine Primzahl ist, liegt hier sogar der endliche Körper $\Bbb F_2$ vor, der kleinste aller Körper.

Der Restklassenring modulo 3

Bei Division durch 3 entstehen die drei Restklassen

$\mathbf{0} := [0] = \{\ ...\ ; -6; -3; 0; 3; 6; 9; 12;\ ...\ \}$, d.h. die durch 3 teilbaren Zahlen.

$\mathbf{1} := [1] = \{\ ...\ ; -5; -2; 1; 4; 7; 10; 13;\ ...\ \}$, d.h. der Divisionsrest ist 1.

$\mathbf{2} := [2] = \{\ ...\ ; -4; -1; 2; 5; 8; 11; 14;\ ...\ \}$, d.h. der Divisionsrest ist 2.

Berechnen wir $\mathbf{1} + \mathbf{2}$:
Wähle etwa die 4 aus $\mathbf{1}$ und die 8 aus $\mathbf{2}$. Rechne 4 + 8 = 12. 12 ist in $\mathbf{0}$. Also $\mathbf{1} + \mathbf{2} = \mathbf{0}$.

Die Menge $\mathbb{Z}/3\mathbb{Z} = \{\mathbf{0},\mathbf{1},\mathbf{2}\}$ bekommt so die Verknüpfungstabellen:

Addition: + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1

Multiplikation: * 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1

$( \mathbb{Z}/3 \mathbb{Z} ,+,\cdot)$ ist ein Ring, und in diesem Fall sogar ein Körper, der als $\Bbb F_3$ bezeichnet wird (von engl. field).

Der Restklassenring modulo 4

Betrachten wir die Reste bei Division durch 4.

$\mathbb{Z}/4\mathbb{Z} = \{\mathbf{0};\mathbf{1};\mathbf{2};\mathbf{3}\}$ mit

$\mathbf{0} = \{\ ...\ ; -4; 0; 4; 8; 12; 16;\ ...\ \}$

$\mathbf{1} = \{\ ...\ ; -3; 1; 5; 9; 13; 17;\ ...\ \}$

$\mathbf{2} = \{\ ...\ ; -2; 2; 6; 10; 14; 18;\ ...\ \}$

$\mathbf{3} = \{\ ...\ ; -1; 3; 7; 11; 15; 19;\ ...\ \}$

In diesem Restklassenring gilt $\mathbf 2\cdot\mathbf 2 = \mathbf{0}$, d.h. $\mathbf{2}$ ist ein Nullteiler. Die Multiplikation ist also in $\mathbb{Z}/4\mathbb{Z} \,\setminus\,\{\mathbf{0}\}$ nicht abgeschlossen. Die so entstandene Struktur $(\Z/4\Z,+,\cdot)$ ist damit kein Körper (obwohl es einen endlichen Körper $\Bbb F_4$ mit vier Elementen gibt), sondern nur ein kommutativer Ring (der Restklassenring modulo 4), denn Nullteiler besitzen kein multiplikatives Inverses.

Ganzzahlenarithmetik bei Mikroprozessoren

Gängige Mikroprozessoren, wie sie beispielsweise in Computern eingesetzt werden, rechnen bei der Ganzzahlarithmetik in Wirklichkeit in Restklassenringen: Die 16-bit-Integer-Zahlen (oft als short integer bezeichnet) bilden den Restklassenring $\Z/65536\Z$ mit 65536 = 2¹⁶. Beispielsweise liefert die Maschine als Ergebnis der Addition 65535+1 den Wert 0, für $32768\cdot 2$ ergibt sich ebenfalls 0.

Verallgemeinerung

Die Idee der Restklassen lässt sich auch in anderen Ringen als den ganzen Zahlen realisieren. Man definiert dazu den Begriff des Ideals und bildet Restklassen modulo einem Ideal, die ihrerseits einen Ring bilden, den man Faktorring nennt.