de
Seitenbanner
Menu
A-Z
Nachlesen

Potenzieren von Restklassen

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

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 fest gewähltes $n \in \N_0$.

\begin{align*} {[x]}_m^{n+1} &\overset{(1)}{=} {[x]}_m^n \cdot {[x]}_m \\[0.5em] &\overset{(2)}{=} {[x^n]}_m \cdot {[x]}_m \\[0.5em] &\overset{(3)}{=} {[x^n \cdot x]}_m \\[0.5em] &\overset{(4)}{=} {[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$.