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\).