de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Restklassenring
Nachlesen

Restklassenring

Beim Restklassenring modulo einer natürlichen Zahl \(m\) handelt es sich um eine abstrakte Klassifikation der ganzen Zahlen bezüglich ihres Restes bei der Division durch \(m\).

Inhalt

Definition

Für eine natürliche Zahl \(m \in \N\) mit \(m \geq 1\) handelt es sich bei der Menge \(\Z_m\) (auch \(\Z/m\Z\)) um die Menge aller Restklassen bezüglich der Division durch \(m\). Hierbei werden alle ganzen Zahlen \(x \in \Z\), die bei der Division modulo \(m\) denselben (ganzzahligen) Rest lassen, zur Restklasse \({[x]}_m\) zusammengefasst; anstelle der Restklasse \({[x]}_m\) wird häufig der kleinste nichtnegative Vertreter der Restklasse als Repräsentant verwendet, sofern aus dem Kontext heraus klar ist, dass es sich um die Restklassen modulo \(m\) handelt.

\begin{align*} \Z_m = \Z/m\Z &= \Bigl\{ {[0]}_m, {[1]}_m, \ldots, {[m-1]}_m \Bigr\} \\[0.5em] &= \Bigl\{ 0,1,\ldots,m-1 \Bigr\} \end{align*}

Auf dieser Menge können nun zwei zweistellige Verknüpfungen – eine Addition \(\oplus\) und eine Multiplikation \(\odot\) – definiert werden (siehe auch Abschnitt Arithmetische Operationen).

\begin{align*} {[a]}_m \oplus {[b]}_m &= {[a+b]}_m \\[0.5em] {[a]}_m \odot {[b]}_m &= {[a \cdot b]}_m \end{align*}

Die Menge \(\Z_m\) bildet zusammen mit der Addition \(\oplus\) und der Multiplikation \(\odot\) einen (endlichen) kommutativen Ring mit Eins – den Restklassenring \((\Z_m,\oplus,\odot)\).

Handelt es sich beim Modul \(m\) um eine Primzahl \(p\), so bildet die Menge \(\Z_p\) zusammen mit der Addition \(\oplus\) und der Multiplikation \(\odot\) einen (endlichen) Körper – den Restklassenkörper \((\Z_p,\oplus,\odot)\), der auch mit \(\mathbb{F}_p\) bezeichnet wird.

Arithmetische Operationen

Addition

Hauptartikel: Addition von Restklassen

Auf der Menge \(\Z_m\) kann eine Addition \(\oplus\) wie folgt definiert werden:

\[ \begin{array}{c} \oplus: \Z_m \times \Z_m \rightarrow \Z_m \\[0.5em] {[x]}_m \oplus {[y]}_m = {[x+y]}_m \end{array} \]

Anstelle des Operators \(\oplus\) wird für die Addition häufig auch der Operator \(+\) als Schreibweise verwendet.

Subtraktion

Hauptartikel: Subtraktion von Restklassen

Auf der Menge \(\Z_m\) kann eine Subtraktion \(\ominus\) wie folgt definiert werden:

\[ \begin{array}{c} \ominus: \Z_m \times \Z_m \rightarrow \Z_m \\[0.5em] {[x]}_m \ominus {[y]}_m = {[x-y]}_m \end{array} \]

Anstelle des Operators \(\ominus\) wird für die Subtraktion häufig auch der Operator \(-\) als Schreibweise verwendet.

Multiplikation

Hauptartikel: Multiplikation von Restklassen

Auf der Menge \(\Z_m\) kann eine Multiplikation \(\odot\) wie folgt definiert werden:

\[ \begin{array}{c} \odot: \Z_m \times \Z_m \rightarrow \Z_m \\[0.5em] {[x]}_m \odot {[y]}_m = {[x \cdot y]}_m \end{array} \]

Anstelle des Operators \(\odot\) wird für die Subtraktion häufig auch der Operator \(\cdot\) als Schreibweise verwendet.

Potenzieren

Hauptartikel: Potenzieren von Restklassen

Für alle Elemente \({[x]}_m\) der Menge \(\Z_m\) und alle natürlichen Zahlen \(n \in \N_0\) kann die Potenz auf die folgende Art rekursiv definiert werden:

\begin{align*} {[x]}_m^0 &= {[1]_m} \\[0.5em] {[x]}_m^n &= {[x]_m^{n-1} \odot {[x]_m}} \\[1em] \Rightarrow {[x]}_m^n &= {[x^n]}_m \end{align*}

Additives neutrales Element

Beim Element \({[0]}_m\) handelt es sich um das neutrale Element der Addition \(\oplus\). Für alle \({[x]}_m \in \Z_m\) gilt:

\[ {[0]}_m \oplus {[x]}_m = {[x]}_m = {[x]}_m \oplus {[0]}_m. \]

Multiplikatives neutrales Element

Beim Element \({[1]}_m\) handelt es sich um das neutrale Element der Multiplikation \(\odot\). Für alle \({[x]}_m \in \Z_m\) gilt:

\[ {[1]}_m \odot {[x]}_m = {[x]}_m = {[x]}_m \odot {[1]}_m. \]

Additive Inverse

Für jedes Element \({[x]}_m \in \Z_m\) existiert stets ein additives Inverses \({[-x]}_m \in \Z_m\). Es gilt:

\[ {[x]}_m \oplus {[-x]}_m = {[0]}_m = {[-x]}_m \oplus {[x]}_m. \]

Multiplikative Inverse

Ein Element \({[x]}_m \in \Z_m\) besitzt nur dann ein multiplikatives Inverses, wenn es sich bei \({[x]}_m\) um eine prime Restklasse modulo \(\mathbf{m}\) handelt, d. h., falls \(x\) und \(m\) teilerfremd sind; für den größten gemeinsamen Teiler von \(x\) und \(m\) gilt dann entsprechend \(\ggT(x,m)=1\). Das multiplikative Inverse kann in diesem Fall mithilfe des erweiterten euklidischen Algorithmus ermittelt werden.

Die Menge der multiplikativ invertierbaren Elemente von \(\Z_m\) bildet eine Gruppe, die mit \(\Z_m^\times\) (oder auch mit \({(\Z/m\Z)}^\times\)) bezeichnet und prime Restklassengruppe genannt wird. Es handelt sich hierbei um die Einheitengruppe des Rings \(\Z_m\). Die prime Restklassengruppe besitzt genau \(\varphi(m)\) Elemente; bei \(\varphi\) handelt es sich hierbei um die eulersche \(\varphi\)-Funktion.

Beispiele

Der Restklassenring modulo 1

Bei der Menge \(\Z_1 = \Z/1\Z\) handelt es sich um die Menge der Restklassen modulo 1. Diese bildet gemeinsam mit der Addition und der Multiplikation von Restklassen modulo 1 den einelementigen Nullring.

\begin{align*} \Z_1 = \Z/1\Z &= \Bigl\{ {[0]}_1 \Bigr\} \\[0.5em] &= \Bigl\{ \Z \Bigr\} \end{align*}

Der Restklassenring modulo 2

Bei der Menge \(\Z_2 = \Z/2\Z\) handelt es sich um die Menge der Restklassen modulo 2. Diese bildet gemeinsam mit der Addition und der Multiplikation von Restklassen modulo 2 einen Restklassenring.

\begin{align*} \Z_2 = \Z/2\Z &= \Bigl\{ {[0]}_2, {[1]}_2 \Bigr\} \\[0.5em] &= \Bigl\{ 0,1 \Bigr\} \end{align*}

Es handelt sich bei \(\Z_2\) um den zweitkleinsten Restklassenring. Da der Modul 2 eine Primzahl ist, handelt es sich darüber hinaus sogar um einen Körper, der auch als \(\mathbb{F}_2\) bezeichnet wird; hierbei handelt es sich um den kleinsten endlichen Körper.

Der Restklassenring modulo 8

Bei der Menge \(\Z_8 = \Z/8\Z\) handelt es sich um die Menge der Restklassen modulo 8. Diese bildet gemeinsam mit der Addition und der Multiplikation von Restklassen modulo 8 einen Restklassenring.

\begin{align*} \Z_8 = \Z/8\Z &= \Bigl\{ {[0]}_8, {[1]}_8, {[2]}_8, {[3]}_8, {[4]}_8, {[5]}_8, {[6]}_8, {[7]}_8 \Bigr\} \\[0.5em] &= \Bigl\{ 0,1,2,3,4,5,6,7 \Bigr\} \end{align*}

Da es sich bei 8 nicht um eine Primzahl handelt, handelt es sich bei \(\Z_8\) nicht um einen Körper. Beispielsweise besitzt das Element \({[2]_8}\) kein multiplikatives Inverses. Die Menge der invertierbaren Elemente bildet die Einheitengruppe des Rings; es gilt:

\begin{align*} \Z_8^\times = {(\Z/8\Z)}^\times &= \Bigl\{ {[1]}_8, {[3]}_8, {[5]}_8, {[7]}_8 \Bigr\} \\[0.5em] &= \Bigl\{ 1,3,5,7 \Bigr\} \end{align*}

Formale Konstruktion

Auf der Menge der ganzen Zahlen \(\Z\) kann für jede natürliche Zahl \(m \in \N\) mit \(m \geq 1\) die folgende Äquivalenzrelation \(\equiv (\bmod{m})\), die Kongruenzrelation modulo \(m\), definiert werden:

\[ a \equiv b \pmod{m} \Leftrightarrow m \mid (a-b). \]

Die Menge \(\Z_m\) (oder auch \(\Z/m\Z\)) der Restklassen modulo \(m\) kann nun formal als \(\Z_m = \Z / \equiv\) definiert werden, also als die Faktormenge (die Menge der Äquivalenzklassen) der Relation \(\equiv\):

\[ \Z_m = \Z/m\Z = \Bigl\{ {[0]}_m, {[1]}_m, \ldots, {[m-1]}_m \Bigr\}. \]

Auf dieser Menge können nun eine Addition \(\oplus\) und eine Multiplikation \(\odot\) wie folgt definiert werden:

\begin{align*} {[a]}_m \oplus {[b]}_m &= {[a+b]}_m \\[0.5em] {[a]}_m \odot {[b]}_m &= {[a \cdot b]}_m \end{align*}

Hierbei ist es insbesondere wichtig, dass die beiden Verknüpfungen wohldefiniert sind, d. h., dass die Ergebnisrestklasse lediglich von den verknüpften Restklassen, aber nicht von den konkreten Vertretern der Restklassen, abhängt.

Beweis der Wohldefiniertheit der Addition
Gegeben seien ganze Zahlen \(a_1,a_2,b_1,b_2 \in \Z\) sowie eine natürliche Zahl \(m \in \N\). Es gelte \({[a_1]}_m = {[a_2]_m}\) sowie \({[b_1]}_m = {[b_2]_m}\). Damit die Addition wohldefiniert ist, muss unter diesen Voraussetzungen dann auch \({[a_1+b_1]}_m = {[a_2+b_2]}_m\) gelten. Dies kann wie folgt gezeigt werden:

\[ \begin{array}{l} {[a_1]}_m = {[a_2]}_m \ \wedge\ {[b_1]}_m = {[b_2]}_m \\[0.5em] \quad\overset{(1)}{\Rightarrow} a_1 \equiv a_2 \pmod{m} \ \wedge\ b_1 \equiv b_2 \pmod{m} \\[0.5em] \quad\overset{(2)}{\Rightarrow} m \mid (a_1-a_2) \ \wedge\ m \mid (b_1-b_2) \\[0.5em] \quad\overset{(3)}{\Rightarrow} m \mid \bigl((a_1-a_2) + (b_1-b_2)\bigr) \\[0.5em] \quad\overset{(4)}{\Rightarrow} m \mid \bigl((a_1+b_1) - (a_2+b_2)\bigr) \\[0.5em] \quad\overset{(5)}{\Rightarrow} a_1+b_1 \equiv a_2+b_2 \pmod{m} \\[0.5em] \quad\overset{(6)}{\Rightarrow} {[a_1+b_1]}_m = {[a_2+b_2]}_m \end{array} \]
Erklärungen zu den Schritten
(1)
  • Definition der Restklassen
(2)
  • Definition der Kongruenzrelation
(3)
(4)
(5)
  • Definition der Kongruenzrelation
(6)
  • Definition der Restklassen

Beweis der Wohldefiniertheit der Multiplikation
Gegeben seien ganze Zahlen \(a_1,a_2,b_1,b_2 \in \Z\) sowie eine natürliche Zahl \(m \in \N\). Es gelte \({[a_1]}_m = {[a_2]_m}\) sowie \({[b_1]}_m = {[b_2]_m}\). Damit die Multiplikation wohldefiniert ist, muss unter diesen Voraussetzungen dann auch \({[a_1 \cdot b_1]}_m = {[a_2 \cdot b_2]}_m\) gelten. Dies kann wie folgt gezeigt werden:

\[ \begin{array}{l} {[a_1]}_m = {[a_2]}_m \ \wedge\ {[b_1]}_m = {[b_2]}_m \\[0.5em] \quad\overset{(1)}{\Rightarrow} a_1 \equiv a_2 \pmod{m} \ \wedge\ b_1 \equiv b_2 \pmod{m} \\[0.5em] \quad\overset{(2)}{\Rightarrow} a_1 = q_{a_1} m + r_a \ \wedge \ a_2 = q_{a_2} m + r_a \\[0.5em] \qquad\ \wedge \ b_1 = q_{b_1} m + r_b \ \wedge \ b_2 = q_{b_2} m + r_b \\[0.5em] \quad\overset{(3)}{\Rightarrow} a_1 \cdot b_1 = (q_{a_1}q_{b_1}m + q_{a_1}r_b + r_aq_{b_1}) \cdot m + r_ar_b \\[0.5em] \qquad\ \wedge \ a_2 \cdot b_2 = (q_{a_2}q_{b_2}m + q_{a_2}r_b + r_aq_{b_2}) \cdot m + r_ar_b \\[0.5em] \quad\overset{(4)}{\Rightarrow} a_1 \cdot b_1 \equiv a_2 \cdot b_2 \pmod{m} \\[0.5em] \quad\overset{(5)}{\Rightarrow} {[a_1 \cdot b_1]}_m = {[a_2 \cdot b_2]}_m \end{array} \]
Erklärungen zu den Schritten
(1)
  • Definition der Restklassen
(2)
  • Zerlegungen mit Rest für \(a_1\), \(a_2\), \(b_1\) und \(b_2\)
(3)
  • Ausrechnen der Produkte \(a_1 \cdot b_1\) und \(a_2 \cdot b_2\) mit dem allgemeinen Distributivgesetz
  • Ausklammern von \(m\) in beiden Produkten
(4)
  • Gemäß den in (3) vorliegenden Zerlegungen mit Rest haben \(a_1 \cdot b_1\) und \(a_2 \cdot b_2\) denselben Rest \(r_ar_b\) bezüglich Division modulo \(m\) und sind somit kongruent
(5)
  • Definition der Restklassen