imported>Rigormath: /* Eigenschaften */ Auch für n = 0 ist a + nℤ doch definiert.

2026-02-16T08:47:50Z

Eigenschaften: Auch für n = 0 ist a + nℤ doch definiert.

Neue Seite

{{Dieser Artikel|beschäftigt sich mit Restklassenringen der ganzen Zahlen modulo einer festen positiven ganzen Zahl. Für allgemeinere Restklassenringe siehe [[Faktorring]].}}
[[Datei:Zahl 60.png|thumb|300px|Der Restklassenring <math>\mathbb{Z}/60\mathbb{Z}</math> graphisch dargestellt. Nähere Erläuterung bei Klick auf das Bild in dessen Beschreibung.]]
In der [[Mathematik]] ist ein '''Restklassenring''' [[modulo]] einer positiven ganzen Zahl <math>n</math> eine Abstraktion der Klassifikation ganzer Zahlen hinsichtlich ihres Restes bei der Division durch <math>n</math>.

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 <math>n\geq 1</math> eine [[natürliche Zahl]], dann werden ganze Zahlen mit gleichem Rest bei [[Division mit Rest|Division]] durch <math>n</math> zu sogenannten ''[[Restklasse]]n'' modulo <math>n</math> zusammengefasst. Zwei ganze Zahlen sind also in derselben Restklasse modulo <math>n</math>, wenn ihre Differenz durch <math>n</math> teilbar ist. Die Restklassen bilden zusammen mit der unten erklärten Addition und Multiplikation den ''Restklassenring modulo n,'' der mit <math>\mathbb{Z}/n\mathbb{Z}</math>, <math>\mathbb Z/(n)</math>, <math>\mathbb Z/n</math> oder <math>\mathbb{Z}_n</math> bezeichnet wird (sprich „Z [[modulo]] n“). Auch für <math>n=0</math> kann man den Restklassenring bilden: Jede ganze Zahl <math>a</math> bildet dann eine eigene Restklasse, weil <math>a-a=0</math> die einzige Differenz <math>\Delta z</math> ist, die durch 0 teilbar ist (für die es eine ganze Zahl <math>t</math> mit <math>\Delta z=t\cdot 0</math> gibt).

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 <math>a</math> mit <math>[a]</math>, dann definiert man:
:<math>[a]+[b]:=[a+b]</math>
:<math>[a] \cdot[b]:=[a\cdot b]</math>

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

Sind <math>a_1,\ b_1,\ a_2,\ b_2</math> ganze Zahlen mit
:<math>[a_1] = [b_1]</math>
<math>[a_2] = [b_2]</math>,
dann gilt:
:<math>[a_1 + a_2] = [b_1 + b_2]</math>
:<math>[a_1 \cdot a_2] = [b_1 \cdot b_2]</math>
Die Verknüpfungen sind also unabhängig vom [[Äquivalenzrelation|Repräsentanten]] der Restklasse definiert.

== Schreibweisen und Konventionen ==

Die Schreibweise <math>\Z_n</math> birgt Verwechslungsgefahr mit der Bezeichnung <math>\Z_p</math> für den Ring der ganzen [[P-adische Zahl|''p''-adischen Zahlen]] zu einer Primzahl <math>p</math>. Wird die Schreibweise <math>\Z_n</math> für den Restklassenring favorisiert, so werden die <math>p</math>-adischen Zahlen mit <math>\Z_p^\land</math> bezeichnet. Die Schreibweise <math>\Z/n\Z</math> für die Restklassenringe, an der präzise die Konstruktion des betreffenden Rings als allgemeiner [[Faktorring]] abzulesen ist, ist umständlicher, aber deutlicher. Die Schreibweise <math>\Z/n</math> ist seltener und auch ungünstig wegen der Verwechslungsgefahr mit <math>\textstyle{\frac1n \Z = \left\{\frac k n\colon k\in\Z\right\}}</math>.

Um die lästige Schreibweise für die Äquivalenzklassen zu vermeiden, lässt man einfach die eckigen Klammern weg. Damit hat für <math>n>0</math> jede Äquivalenzklasse unendlich viele Namen; beispielsweise gelten mit der vereinbarten Schreibweise für die Äquivalenzklassen <math>[0]</math> und <math>[n-1]</math> die Gleichungen <math>0=n=-n</math> beziehungsweise <math>n-1=2n-1=-1</math> in <math>\Z/n\Z</math>. 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 <math>(\Z_n, +, \cdot)</math> besteht nach dieser Konvention aus den Zahlen <math>0, 1, \dotsc, n-1</math>.
Durch die Verknüpfungen
:<math>(a + b) \mod n</math>
:<math>(a\ \cdot\ b) \mod n</math>
im Ring <math>\Z</math> der ganzen Zahlen erhalten wir Ergebnisse, die wir nach unserer Konvention nun sofort als Ergebnisse in <math>\Z_n</math> interpretieren dürfen.
Jede Kette arithmetischer Operationen in diesem Restklassenring (z. B. die Auswertung eines Polynoms <math>p\in\Z_n[X]</math> an der Stelle <math>X=k</math> mit <math>k\in\Z_n</math>) 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 <math>n=2^k</math> eine Zweierpotenz, so wird oft auch das um die Null symmetrisierte [[Vertretersystem]] <math>\textstyle{\left\{-\tfrac{n}{2}, \dotsc, -1, 0, 1, \dotsc, \tfrac{n}{2}-1\right\}}</math> gewählt. Dieses korrespondiert nämlich mit einer Binärdarstellung der Zahlen, bei der das höchstwertige Bit als [[Vorzeichen (Zahl)|Vorzeichen]] interpretiert wird.

== Eigenschaften ==

Für jede natürliche Zahl <math>n \geq 0</math> ist <math>\mathbb{Z}/n\mathbb{Z}</math> ein kommutativer [[Ring mit Eins]]. Das Nullelement ist die Restklasse <math>[0] = n\mathbb{Z}</math> und das Einselement die Restklasse <math>[1] = 1 + n\Z</math>. Für <math>n=1</math> ist dieser Ring der [[Nullring]]; einziges Element ist die alle ganzen Zahlen umfassende Restklasse <math>[0] = \Z</math>, die hierbei zugleich Einselement ist. Für <math>n=0</math> ist der Restklassenring [[isomorph]] zum Ring <math>\mathbb{Z}</math> selbst.

Ist <math>p</math> eine [[Primzahl]], dann ist der Restklassenring <math>\mathbb{Z}/p\mathbb{Z}</math> ein [[endlicher Körper]], der [[Restklassenkörper]] modulo <math>p</math>, und wird mit <math>\mathbb F_p</math> (von engl. „field“ für Körper) bezeichnet. Insbesondere besitzt darin jede Restklasse <math>[a] \ne [0]</math> (bei der also <math>a</math> nicht durch <math>p</math> [[teilbar]] ist) eine [[Inverses Element|Inverse]] bezüglich der Multiplikation.

Ist dagegen <math>n>1</math>, aber keine Primzahl, dann ist der Restklassenring modulo <math>n</math> kein [[Körper (Algebra)|Körper]], da die Restklasse jedes echten Teilers von <math>n</math> ein [[Nullteiler]] ist, der kein [[Inverses Element|Inverses]] bezüglich der [[Multiplikation]] besitzt. Der Nullring (<math>n=1</math>) sowie <math>\mathbb{Z}</math> selbst (<math>n=0</math>) sind nullteilerfrei, aber ebenfalls keine Körper.

== Invertierbarkeit und Inversenberechnung ==
Zugrunde gelegt sei der Restklassenring <math>\Z/n\Z\,</math> (<math>n \ge 1</math>) oder auch – weil nun dessen Addition keine Rolle spielt – nur das kommutative [[Monoid]] <math>(\Z/n\Z,\,\cdot\,).</math> Darin ist eine Restklasse <math>[a]</math> genau dann [[Inverses Element|invertierbar]] (bezüglich der Multiplikation), wenn es eine Restklasse <math>[x]</math> gibt mit
:<math>
[a] \cdot [x] = [1],\quad</math> d. h. <math>\quad ax \equiv 1 \!\pmod{\!n},
</math>
wenn es also zwei ganze Zahlen <math>x</math> und <math>y</math> gibt mit
:<math>
ax + ny = 1,
</math>
d. h. wenn gilt:
:<math>
\mathrm{ggT}(n,a) = 1
</math>
(siehe [[Lineare diophantische Gleichung]]). In diesem Fall ist die Restklasse <math>[x]</math> die [[Inverses Element|Inverse]] von <math>[a],</math> kurz <math>\textstyle [a]^{-1} = [x].</math> Mit dem [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] lassen sich zu den beiden ganzen Zahlen <math>n \ge 1</math> und <math>a</math> allgemein <math>g = \mathrm{ggT}(n,a)</math> und zwei ganze Zahlen <math>x,</math> <math>y</math> mit <math>ax + ny = g</math> berechnen.

[[Datei:Roland Uhl - Inverse Restklasse.svg|hochkant=1.8|rahmenlos|rechts|rand|Erweiterter euklidischer Algorithmus für g = ggT(34,15)]]
Beispielsweise ist im Restklassenring <math>\Z/n\Z</math> mit <math>n = 34</math> die Restklasse von <math>a = 15</math> invertierbar mit der Inversen
:<math>
[15]^{-1} = [-9] </math> <math> = [-9 + 34] = [25].
</math>
Denn es gilt
:<math>
g = \mathrm{ggT}(n,a) = 1 = 4n - 9a
</math>
nach der nebenstehenden Rechnung. So wird im ersten Rechenschritt entsprechend zu „<math>34:15</math> ergibt <math>2</math> Rest <math>4</math>“ ([[Division mit Rest]]) das <math>(-2)</math>-Fache der Gleichung <math>15 = 0n + 1a</math> zur Gleichung <math>34 = 1n + 0a</math> addiert, was zu <math>4 = 1n - 2a</math> führt. Sobald sich links Rest <math>0</math> ergibt, steht darüber <math>g\,</math> (bzw. allgemein <math>\pm g,</math> falls man auch negative Reste zulässt). Bei dem entsprechenden Zahlenschema ganz rechts mit den analogen Zeilenoperationen könnte man offenbar die <math>n</math>-Spalte weglassen. Abschließend lässt sich <math>\textstyle [15]^{-1} = [-9]</math> direkt überprüfen:
:<math>
[15] \cdot [-9] = [-135] = [-135 + 4\cdot 34] = [1]
</math>
in <math>\Z/34\Z.</math>

Allgemein heißen die invertierbaren Restklassen in <math>\Z/n\Z\,</math> (<math>n \ge 1</math>) auch prime Restklassen modulo <math>n.</math> Sie bilden zusammen eine [[abelsche Gruppe]] bezüglich der Multiplikation, die man [[prime Restklassengruppe]] modulo <math>n</math> nennt und mit <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> bezeichnet. Sie ist die [[Einheitengruppe]] des Rings <math>\mathbb{Z}/n\mathbb{Z}</math> und hat <math>\varphi(n)</math> Elemente, wobei <math>\varphi</math> 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 1 bis 12 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 <math>4 + 5</math> zu ermitteln, beginnt man bei Stunde 4 und zählt fünf Stunden weiter, man landet bei Stunde 9. Berechnet man nun <math>9 + 5</math>, zählt also von Stunde 9 aus fünf Stunden weiter, landet man bei Stunde 2, es ist also <math>9 + 5 = 2</math> 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 <math>14 = 2</math>. Das Ergebnis einer Addition ist also die normale Summe, eventuell abzüglich einer Zwölf. Dies entspricht dem [[Division mit Rest|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, <math>12 + x = x</math> für jede Stunde <math>x</math>. Das erklärt, warum die 12. Stunde hier als Stunde 0 bezeichnet wird.

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

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

Entsprechend funktioniert auch die Berechnung der Minuten auf dem Zifferblatt einer Analoguhr. Die Minuten sind von 0 bis 59 nummeriert und entsprechend erhält man in <math>\mathbb{Z} / 60\mathbb{Z} = \{0, 1, \dotsc, 58 , 59\}</math> beispielsweise <math>15 + 30 = 45, \ 30 + 30 = 0, \ 45 + 30 = 15</math> usw.
Das Rechnen mit Restklassen findet sich auch in der Berechnung von Tagen, die auf 24 Stunden begrenzt sind und in Wochen, die aus 7 Tagen bestehen und dann entsprechend nicht auf einer Menge von Zahlen, sondern von Tagesbezeichnungen definiert ist, also beispielsweise „5 Tage nach Freitag ist Mittwoch, 5 Tage vor Mittwoch ist Freitag“.

=== Der Restklassenring modulo 2 ===

[[Datei:Restklassenring modulo 2.png|thumb|120px|Der Restklassenring <math>\mathbb{Z}/2\mathbb{Z}</math> graphisch dargestellt]]
Bei Division ganzer Zahlen durch 2 mit Rest ergibt sich als Rest entweder 0 oder 1. Damit ist <math>\Z / 2\Z = \Z_2 = \{0, 1\}</math> nach dem einelementigen [[Nullring]] <math>\Z / 1\Z = \Z_1 = \{\Z\}</math> der zweitkleinste aller Restklassenringe. Da 2 eine Primzahl ist, liegt hier sogar der endliche Körper <math>\mathbb F_2</math> vor, der kleinste aller Körper.

=== Der Restklassenring modulo 3 ===

[[Datei:Restklassenring modulo 3.png|thumb|120px|Der Restklassenring <math>\mathbb{Z}/3\mathbb{Z}</math> graphisch dargestellt.]]
Bei Division durch 3 entstehen die drei Restklassen
:<math>\mathbf{0} := [0] = \{\dotsc, -6, -3, 0, 3, 6, 9, 12, \dotsc\}</math>, d. h. die durch 3 teilbaren Zahlen.
:<math>\mathbf{1} := [1] = \{\dotsc, -5, -2, 1, 4, 7, 10, 13, \dotsc\}</math>, d. h., der Divisionsrest ist 1.
:<math>\mathbf{2} := [2] = \{\dotsc, -4, -1, 2, 5, 8, 11, 14, \dotsc\}</math>, d. h., der Divisionsrest ist 2.

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

Die Menge <math>\mathbb{Z}/3\mathbb{Z} = \{\mathbf{0}, \mathbf{1}, \mathbf{2}\}</math> bekommt so die Verknüpfungstabellen:
{|
|-----
|
''Addition:''
{| border="1" cellspacing="0" cellpadding="5" style="border-collapse:collapse;"
|-----
|<math> + </math>|| '''''0''''' || '''''1''''' || '''''2'''''
|-----
| '''''0''''' || ''0'' || ''1'' || ''2''
|-----
| '''''1''''' || ''1'' || ''2'' || ''0''
|-----
| '''''2''''' || ''2'' || ''0'' || ''1''
|}
| width="75" | ||
''Multiplikation:''
{| border="1" cellspacing="0" cellpadding="5" style="border-collapse:collapse;"
|-----
|<math> \cdot </math>|| '''''0''''' || '''''1''''' || '''''2'''''
|-----
| '''''0''''' || ''0'' || ''0'' || ''0''
|-----
| '''''1''''' || ''0'' || ''1'' || ''2''
|-----
| '''''2''''' || ''0'' || ''2'' || ''1''
|}
|}

<math>(\mathbb{Z}/3 \mathbb{Z}, +, \cdot)</math> ist ein Ring und, da 3 eine [[Primzahl]] ist, sogar ein [[Körper (Algebra)|Körper]], der als <math>\mathbb F_3</math> bezeichnet wird (von engl. ''field'').

=== Der Restklassenring modulo 4 ===

[[Datei:Restklassenring modulo 4.png|thumb|120px|Der Restklassenring <math>\mathbb{Z}/4\mathbb{Z}</math> graphisch dargestellt]]
Betrachten wir die Reste bei Division durch 4.

Es gilt <math>\mathbb{Z}/4\mathbb{Z} = \{\mathbf{0}, \mathbf{1}, \mathbf{2}, \mathbf{3}\}</math> mit:
:<math>\mathbf{0} = \{\dotsc, -4, 0, 4, 8, 12, 16, \dotsc\}</math>
:<math>\mathbf{1} = \{\dotsc, -3, 1, 5, 9, 13, 17, \dotsc\}</math>
:<math>\mathbf{2} = \{\dotsc, -2, 2, 6, 10, 14, 18, \dotsc\}</math>
:<math>\mathbf{3} = \{\dotsc, -1, 3, 7, 11, 15, 19, \dotsc\}</math>

In diesem Restklassenring gilt <math>\mathbf 2\cdot\mathbf 2 = \mathbf{0}</math>, d. h. <math>\mathbf{2}</math> ist ein [[Nullteiler]]. Die Multiplikation ist also in <math>\mathbb{Z}/4\mathbb{Z}\setminus\{\mathbf{0}\} </math> nicht abgeschlossen.
Die so entstandene Struktur <math>(\Z/4\Z, +, \cdot)</math> ist damit kein Körper, sondern nur ein kommutativer ''Ring'' (der Restklassenring modulo 4), denn Nullteiler besitzen kein multiplikatives [[Inverses Element|Inverses]]. Dies hängt damit zusammen, dass 4 keine [[Primzahl]] ist und somit <math>\mathbb{Z}/4\mathbb{Z}</math> kein [[Integritätsring]] ist. (Jedoch gibt es, da <math>4 = 2^2</math> eine Potenz einer Primzahl ist, einen ''anderen'' Körper, der vier Elemente hat.)

=== Ganzzahlarithmetik bei Mikroprozessoren ===

Gängige [[Mikroprozessor]]en, wie sie beispielsweise in Computern eingesetzt werden, rechnen bei der Ganzzahlarithmetik in Wirklichkeit in Restklassenringen: Die vorzeichenlosen 16-bit-Integer-Zahlen (oft als ''unsigned short integer'' bezeichnet) bilden den Restklassenring <math>\Z/65536\Z</math> mit <math>65536=2^{16}</math>. Beispielsweise liefert die Maschine als Ergebnis der Addition 65535+1 den Wert 0, für 32768·2 ergibt sich ebenfalls 0.

== Verallgemeinerung ==

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

[[Kategorie:Ring (Algebra)]]
[[Kategorie:Ringtheorie]]
[[Kategorie:Zahlentheorie]]

== Literatur ==

* Andreas Bartholomé, Josef Rung, Hans Kern: ''Zahlentheorie für Einsteiger.'' Vieweg+Teubner, 7. Auflage, 2010, ISBN 978-3-8348-1213-1.

Restklassenring - Versionsgeschichte

imported>Rigormath: /* Eigenschaften */ Auch für n = 0 ist a + nℤ doch definiert.