de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Restklassenring
  • Operationen
  • Potenzieren von Restklassen
Nachlesen

Potenzieren von Restklassen

Beim Potenzieren einer Restklasse wird die Potenz einer Restklasse bestimmt, indem die Restklasse der Potenz ihres Repräsentanten bestimmt wird.

Inhalt

Definition

Gegeben seien eine ganze Zahl \(x \in \Z\) sowie zwei natürliche Zahlen \(m \in \N\) und \(n \in \N_0\). Für ein Element \({[x]}_m\) des Restklassenrings \(\Z_m\) wird die \(\mathbf{n}\)-te Potenz der Restklasse wie folgt rekursiv definiert:

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

Alternativ kann die \(n\)-te Potenz wie folgt explizit definiert werden:

\[ {[x]}_m^n = {[x^n]}_m. \]

Beispiele

Beispiel 1

Es soll die Potenz \({[2]}_5^8\) berechnet werden. Gemäß der (expliziten) Definition für Potenzen von Restklassen modulo \(m\) ergibt sich:

\begin{align*} {[2]}_5^8 &= {[2^8]}_5 \\[0.5em] &= {[256]}_5 \\[0.5em] &= {[1]}_5 \end{align*}

Da es sich bei \({[256]}_5\) nicht um den Standardvertreter der Restklasse handelt, wird das Zwischenergebnis im letzten Schritt entsprechend umgerechnet.

Beispiel 2

Es soll die Potenz \({[7]}_{13}^3\) berechnet werden. Gemäß der (rekursiven) Definition für Potenzen von Restklassen modulo \(m\) ergibt sich:

\begin{align*} {[7]}_{13}^3 &= {[7]}_{13}^2 \odot {[7]}_{13} \\[0.5em] &= {[10]}_{13} \odot {[7]}_{13} \\[0.5em] &= {[5]}_{13} \end{align*}

Eigenschaften

Assoziativität

Das Potenzieren von Restklassen modulo $m$ ist im Allgemeinen nicht assoziativ, wie das folgende Beispiel zeigt:

\begin{align*} {\bigl( {[2]}_5^3 \bigr)}^2 = {[3]}_5^2 &= {[4]}_5 \\[0.5em] {[2]}_5^{\bigl( 3^2 \bigr)} = {[2]}_5^9 &= {[2]}_5 \end{align*}

Das Potenzieren von Restklassen modulo \(m\) ist linksassoziativ.

Kommutativität

Das Potenzieren von Restklassen modulo $m$ ist nicht kommutativ, da das Potenzieren einer natürlichen Zahl mit einer Restklasse modulo \(m\) undefiniert ist.

Neutrales Element

Es existiert kein neutrales Element bzgl. des Potenzierens von Restklassen modulo $m$. Das Element \(n=1\) ist rechtsneutral.

Inverses Element

Das inverse Element eines Elements \({[x]}_m\) bezüglich des Potenzierens modulo \(m\) existiert nicht. Das Verknüpfen eines Elements mit seinem Inversen muss stets das neutrale Element ergeben, welches für das Potenzieren aber nicht existiert.

Beweis

Die Aussage \({[x]}_m^n = {[x^n]}_m\) kann mittels vollständiger Induktion bewiesen werden, indem die Aussage durch Nachrechnen zunächst für ein spezielles \(n\) (z. B. für \(n=0\)) überprüft wird und anschließend gezeigt wird, dass unter der Annahme, die Aussage gelte für ein konkretes \(n\), dann auch die entsprechende Aussage für dessen Nachfolger \(n+1\) gilt.

(I) Induktionsanfang
Die Aussage ist für \(n=0\) gültig, denn es gilt

\begin{align*} {[x]}_m^0 &= {[1]}_m \\[0.5em] {[x^0]}_m &= {[1]}_m. \end{align*}

(II) Induktionsschritt
Induktionsannahme: Die Behauptung gelte für ein festes \(n \in \N_0\).

\begin{align*} {[x]}_m^{n+1} &\overset{(1)}{=} {[x]}_m^n \cdot {[x]}_m \\[0.5em] &\overset{(2)}{\equiv} {[x^n]}_m \cdot {[x]}_m \\[0.5em] &\overset{(3)}{\equiv} {[x^n \cdot x]}_m \\[0.5em] &\overset{(4)}{\equiv} {[x^{n+1}]}_m \end{align*}
Erklärungen zu den Schritten
(1)
  • Zurückführen von \({[x]}_m^{n+1}\) auf \({[x]}_m^n\) mithilfe der Definition der Potenzen von Restklassen modulo \(m\)
(2)
  • Ersetzen von \({[x]}_m^n\) mithilfe der Induktionsannahme
(3)
(4)

Insgesamt folgt, dass die Behauptung für \(n+1\) gilt, falls sie für \(n\) gilt. Gemeinsam mit dem Induktionsanfang folgt somit die Gültigkeit der Kongruenz \({[x]}_m^n = {[x^n]}_m\) für alle \(n \in \N_0\).