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

Der Restklassenring graphisch dargestellt. Nähere Erläuterung bei Klick auf das Bild in dessen Beschreibung.

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

Bearbeiten

Ist   eine natürliche Zahl, dann werden ganze Zahlen mit gleichem Rest bei Division durch   zu sogenannten Restklassen modulo   zusammengefasst. Zwei ganze Zahlen sind also in derselben Restklasse modulo  , wenn ihre Differenz durch   teilbar ist. Die Restklassen bilden zusammen mit der unten erklärten Addition und Multiplikation den Restklassenring modulo n, der mit  ,  ,   oder   bezeichnet wird (sprich „Z modulo n“). Auch für   kann man den Restklassenring bilden: Jede ganze Zahl   bildet dann eine eigene Restklasse, weil   die einzige Differenz   ist, die durch 0 teilbar ist (für die es eine ganze Zahl   mit   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   mit  , dann definiert man:

 
 

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

Sind   ganze Zahlen mit

 

 , dann gilt:

 
 

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

Schreibweisen und Konventionen

Bearbeiten

Die Schreibweise   birgt Verwechslungsgefahr mit der Bezeichnung   für den Ring der ganzen p-adischen Zahlen zu einer Primzahl  . Wird die Schreibweise   für den Restklassenring favorisiert, so werden die  -adischen Zahlen mit   bezeichnet. Die Schreibweise   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   ist seltener und auch ungünstig wegen der Verwechslungsgefahr mit  .

Um die lästige Schreibweise für die Äquivalenzklassen zu vermeiden, lässt man einfach die eckigen Klammern weg. Damit hat für   jede Äquivalenzklasse unendlich viele Namen; beispielsweise gelten mit der vereinbarten Schreibweise für die Äquivalenzklassen   und   die Gleichungen   beziehungsweise   in  . 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   besteht nach dieser Konvention aus den Zahlen  . Durch die Verknüpfungen

 
 

im Ring   der ganzen Zahlen erhalten wir Ergebnisse, die wir nach unserer Konvention nun sofort als Ergebnisse in   interpretieren dürfen. Jede Kette arithmetischer Operationen in diesem Restklassenring (z. B. die Auswertung eines Polynoms   an der Stelle   mit  ) 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   eine Zweierpotenz, so wird oft auch das um die Null symmetrisierte Vertretersystem   gewählt. Dieses korrespondiert nämlich mit einer Binärdarstellung der Zahlen, bei der das höchstwertige Bit als Vorzeichen interpretiert wird.

Eigenschaften

Bearbeiten

Für jede natürliche Zahl   ist   ein kommutativer Ring mit Eins. Das Nullelement ist die Restklasse   und das Einselement die Restklasse  . Für   ist dieser Ring der Nullring; einziges Element ist die alle ganzen Zahlen umfassende Restklasse  , die hierbei zugleich Einselement ist. Für   sind Restklassen der Form   nicht definiert; der dennoch definierbare Restklassenring (siehe Definition oben) ist bis auf Isomorphie der Ring   selbst.

Ist   eine Primzahl, dann ist der Restklassenring   ein endlicher Körper, der Restklassenkörper modulo  , und wird mit   (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  , aber keine Primzahl, dann ist der Restklassenring modulo   kein Körper, da die Restklasse jedes echten Teilers von   ein Nullteiler ist, der kein Inverses bezüglich der Multiplikation besitzt. Der Nullring ( ) sowie   selbst ( ) sind nullteilerfrei, aber ebenfalls keine Körper.

Eine Restklasse   mit   (mit  ) heißt prime Restklasse modulo  . Die Gruppe der primen Restklassen modulo   heißt prime Restklassengruppe modulo   und wird mit   symbolisiert. Sie ist die Einheitengruppe des Rings   und hat   Elemente, wobei   die eulersche φ-Funktion ist.

Beispiele

Bearbeiten

Veranschaulichung am Zifferblatt der Uhr

Bearbeiten

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   zu ermitteln, beginnt man bei Stunde 4 und zählt fünf Stunden weiter, man landet bei Stunde 9. Berechnet man nun  , zählt also von Stunde 9 aus fünf Stunden weiter, landet man bei Stunde 2, es ist also   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  . 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,   für jede Stunde  . Das erklärt, warum die 12. Stunde hier als Stunde 0 bezeichnet wird.

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

Die zwölf Stundenwerte, zusammen mit den Regeln für Addition und Multiplikation, schreibt man als  .

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   beispielsweise   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

Bearbeiten
 
Der Restklassenring   graphisch dargestellt

Bei Division ganzer Zahlen durch 2 mit Rest ergibt sich als Rest entweder 0 oder 1. Damit ist   nach dem einelementigen Nullring   der zweitkleinste aller Restklassenringe. Da 2 eine Primzahl ist, liegt hier sogar der endliche Körper   vor, der kleinste aller Körper.

Der Restklassenring modulo 3

Bearbeiten
 
Der Restklassenring   graphisch dargestellt.

Bei Division durch 3 entstehen die drei Restklassen

 , d. h. die durch 3 teilbaren Zahlen.
 , d. h., der Divisionsrest ist 1.
 , d. h., der Divisionsrest ist 2.

Berechnen wir  :
Wähle etwa die 4 aus   und die 8 aus  . Rechne  . 12 ist in  . Also  .

Die Menge   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

  ist ein Ring und, da 3 eine Primzahl ist, sogar ein Körper, der als   bezeichnet wird (von engl. field).

Der Restklassenring modulo 4

Bearbeiten
 
Der Restklassenring   graphisch dargestellt

Betrachten wir die Reste bei Division durch 4.

Es gilt   mit:

 
 
 
 

In diesem Restklassenring gilt  , d. h.   ist ein Nullteiler. Die Multiplikation ist also in   nicht abgeschlossen. Die so entstandene Struktur   ist damit kein Körper, sondern nur ein kommutativer Ring (der Restklassenring modulo 4), denn Nullteiler besitzen kein multiplikatives Inverses. Dies hängt damit zusammen, dass 4 keine Primzahl ist und somit   kein Integritätsring ist. (Jedoch gibt es, da   eine Potenz einer Primzahl ist, einen anderen Körper, der vier Elemente hat.)

Ganzzahlarithmetik bei Mikroprozessoren

Bearbeiten

Gängige Mikroprozessoren, 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   mit  . Beispielsweise liefert die Maschine als Ergebnis der Addition 65535+1 den Wert 0, für 32768·2 ergibt sich ebenfalls 0.

Verallgemeinerung

Bearbeiten

Die Idee der Restklassen lässt sich auch in anderen Ringen als dem der 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.

Literatur

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