de
Seitenbanner
Menu
A-Z
Nachlesen

Modulares Potenzieren

Beim modularen Potenzieren (auch Potenzieren modulo m) kann der Rest der Potenz einer ganzen Zahl bei Division durch $m$ alternativ über die kongruente Potenz des Rests der Zahl bestimmt werden.

Definition

Gegeben seien eine ganze Zahl $a \in \Z$ sowie zwei natürliche Zahlen $m \in \N$ und $n \in \N_0$. Mit $r_a$ sei der ganzzahlige Rest der Division von $a$ durch $m$ bezeichnet. Für das modulare Potenzieren gilt die folgende Kongruenz:

\[ a^n \equiv r_a^n \pmod{m}. \]

In Worten lässt sich dies wie folgt ausdrücken: Der Rest der Potenz ist kongruent zur Potenz des Restes.

Beispiele

Beispiel 1

Es soll die Potenz $23^2 \pmod{5}$ berechnet werden. Mithilfe der Kongruenz $23 \equiv 3 \pmod{5}$ ergibt sich die folgende Lösung:

\[ 23^2 \equiv 3^2 \equiv 9 \equiv 4 \pmod{5}. \]

Ausrechnen der Originalpotenz zu Vergleichszwecken liefert dasselbe Ergebnis:

\[ 23^2 = 529 \equiv 4 \pmod{5}. \]

Beispiel 2

Es soll die Potenz $42^{10} \pmod{5}$ berechnet werden. Mithilfe der Kongruenz $42 \equiv 2 \pmod{5}$ ergibt sich die folgende Lösung:

\[ 42^{10} \equiv 2^{10} \equiv 1\,024 \equiv 4 \pmod{5}. \]

Ausrechnen der Originalpotenz zu Vergleichszwecken liefert dasselbe Ergebnis:

\[ 42^{10} = 17\,080\,198\,121\,677\,824 \equiv 4 \pmod{5}. \]

Hinweis: Höhere Potenzen können beispielsweise mithilfe des Square-and-Multiply-Verfahrens effizient berechnet werden.

Eigenschaften

Assoziativität

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

\begin{align*} \begin{alignedat}{2} {\bigl( 2^3 \bigr)}^2 &= 64 \equiv 4 && \pmod{5} \\[0.5em] 2^{\bigl( 3^2 \bigr)} &= 512 \equiv 2 && \pmod{5} \end{alignedat} \end{align*}

Das Potenzieren modulo $m$ ist linksassoziativ.

Kommutativität

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

\begin{align*} \begin{alignedat}{2} 2^3 &= 8 \equiv 3 \pmod{5} \\[0.5em] 3^2 &= 9 \equiv 4 \pmod{5} \end{alignedat} \end{align*}

Neutrales Element

Es existiert kein neutrales Element bzgl. des Potenzierens modulo $m$. Das Element $n=1$ ist rechtsneutral.

Inverses Element

Das inverse Element einer Zahl $a$ 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

Gegeben seien eine ganze Zahl $a \in \Z$ sowie zwei natürliche Zahlen $m \in \N$ und $n \in N_0$. Für $a$ existiert die folgenden Zerlegung mit Rest (mit $q_a,r_a \in \Z$ sowie $0 \leq r_a \lt m$):

\[ a = q_a \cdot m + r_a. \]

Beweis durch Nachrechnen

Die Aussage kann durch Nachrechnen direkt bewiesen werden. Für die Potenz $a^n$ gilt:

\begin{align*} a^n &\overset{(1)}{=} {(q_a \cdot m + r_a)}^n \\[0.5em] &\overset{(2)}{=} \sum\limits_{k=0}^{n}{\binom{n}{k} {(q_a \cdot m)}^k \cdot r_a^{n-k}} \\[0.5em] &\overset{(3)}{=} \underbrace{\binom{n}{0}{(q_a \cdot m)}^0}_{=\ 1} \cdot r_a^{n-0} + \sum\limits_{k=1}^{n}{\binom{n}{k} q_a^k \cdot m^k \cdot r_a^{n-k}} \\[0.5em] &\overset{(4)}{=} r_a^n + \underbrace{m \cdot \sum\limits_{k=1}^{n}{\binom{n}{k} q_a^k \cdot m^{k-1} \cdot r_a^{n-k}}}_{\equiv\ 0 \pmod{m}} \\[0.5em] &\overset{(5)}{\equiv} r_a^n \pmod{m} \end{align*}
Erklärungen zu den Schritten
(1)
  • Ersetzen von $a$ durch die zugehörige Zerlegung mit Rest
(2)
(3)
  • Herausziehen des Summanden für $k=0$ aus der Summe
  • Anwenden von Potenzgesetz I-a für $ {(q_a \cdot m)}^k$
(4)
  • Herausziehen des konstanten Faktors $m$ aus der Summe
(5)

Beweis mithilfe vollständiger Induktion

Die Aussage 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*} a^0 &= 1 \\[0.5em] r_a^0 &= 1 \\[0.5em] \Rightarrow a^0 &= r_a^0 \\[0.5em] \Rightarrow a^0 &\equiv r_a^0 \pmod{m}. \end{align*}

(II) Induktionsschritt
Induktionsannahme: Die Behauptung gelte für ein fest gewähltes $n \in \N_0$.

\begin{align*} \begin{alignedat}{2} a^{n+1} &\overset{(1)}{=} a^n \cdot a && \\[0.5em] &\overset{(2)}{\equiv} r_a^n \cdot r_a && \pmod{m} \\[0.5em] &\overset{(3)}{\equiv} r_a^{n+1} && \pmod{m} \end{alignedat} \end{align*}
Erklärungen zu den Schritten
(1)
(2)
(3)
  • Zusammenfassen mithilfe von Potenzgesetz I-a

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 $a^n \equiv r_a^n \pmod{m}$ für alle $n \in \N_0$.