Nachlesen

Multiplikative Inverse von Restklassen

Beim multiplikativen Inversen einer Restklasse \({[x]}_m\) handelt es sich – falls existent – um diejenige Restklasse, die mit \({[x]}_m\) multipliziert das neutrale Element \({[1]}_m\) ergibt. Es kann beispielsweise mit dem erweiterten euklidischen Algorithmus ermittelt werden.

Definition

Gegeben sei eine ganze Zahl \(x \in \Z\) sowie eine natürliche Zahl \(m \in \N\). Beim multiplikativen Inversen des Elements \({[x]}_m\) des Restklassenrings \(\Z_m\) handelt es sich – falls existent – um das Element \({[x]}_m^{-1} \in \Z_m\), für das gilt:

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

Handelt es sich bei \({[x]}_m^{-1}\) um das multiplikative Inverse von \({[x]}_m\), so handelt es sich umgekehrt bei \({[x]}_m\) auch stets um das multiplikative Inverse von \({[x]}_m^{-1}\). Es ist nicht notwendig, dass es sich bei \({[x]}_m\) und \({[x]}_m^{-1}\) um verschiedene Elemente handelt; das Element \({[x]}_m\) ist in diesem Fall zu sich selbst invers. Dies ist beispielsweise für die Elemente \({[1]}_m\) und \({[m-1]}_m\) immer der Fall.

Allgemein gilt: 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\).

Beschreibung des Verfahrens

Berechnung mithilfe des erweiterten euklidischen Algorithmus

Die Berechnung des multiplikativen Inversen eines Elements \({[x]}_m\) kann mithilfe des erweiterten euklidischen Algorithmus durchgeführt werden. Hierzu wird zunächst der größte gemeinsame Teiler der Zahlen \(x\) und \(m\) berechnet. Falls die Zahlen nicht teilerfremd sind, falls also \(\ggT(x,m) \neq 1\) gilt, so existiert kein multiplikatives Inverses; sind die beiden Zahlen hingegen teilerfremd, gilt also \(\ggT(x,m)=1\), so können mithilfe des erweiterten euklidischen Algorithmus (garantiert durch das Lemma von Bézout) anschließend Parameter \(s,t \in \Z\) gefunden werden, für die gilt:

\ggT(x,m) = 1 = s \cdot x + t \cdot m.

Aus dieser Gleichheit ergibt sich unmittelbar die folgende Kongruenz:

\begin{align*} \begin{alignedat}{2} 1 &\equiv s \cdot x + \underbrace{t \cdot m}_{\equiv\ 0} && \pmod{m} \\[0.5em] &\equiv s \cdot x && \pmod{m}. \end{alignedat} \end{align*}

Nach der Definition von Restklassen und der Definition der Multiplikation von Restklassen folgt hieraus

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

Beim gesuchten multiplikativen Inversen \({[x]}_m^{-1}\) handelt es sich also um die Restklasse \({[s]}_m\).

Hinweis: Da der erweiterte euklidische Algorithmus keine Garantie liefert, dass \(0 \leq s \lt m\) gilt, muss \({[s]}_m\) abschließend gegebenenfalls noch in den Standardvertreter der Restklasse umgerechnet werden.

Berechnung mithilfe des Satzes von Euler

Das multiplikative Inverse eines Elements \({[x]}_m\) kann mithilfe des Satzes von Euler durch das Potenzieren der Restklasse \({[x]}_m\) berechnet werden. Für teilerfremde Zahlen \(x\) und \(m\) liefert der Satz von Euler die folgende Kongruenz:

x^{\varphi(m)} \equiv 1 \pmod{m}.

Bei \(\varphi\) handelt es sich um die eulersche \(\varphi\)-Funktion. Gemäß der Definition von Restklassen folgt aus dieser Kongruenz unmittelbar

{[x^{\varphi(m)}]}_m = {[1]}_m.

Aufgrund der Definition der Potenzen von Restklassen ergibt sich hieraus:

\begin{align*} {[1]}_m &= {[x^{\varphi(m)}]}_m \\[0.5em] &= {[x]}_m^{\varphi(m)} \\[0.5em] &= {[x]}_m^{\varphi(m)-1} \odot {[x]}_m. \end{align*}

Das gesuchte multiplikative Inverse \({[x]}_m^{-1} = {[x]}_m^{\varphi(m)-1}\) kann anschließend direkt berechnet werden.

Beispiele

Beispiel 1: Erweiterter euklidischer Algorithmus

Es soll das multiplikative Inverse von \({[42]}_{47}\) in \(\Z_{47}\) berechnet werden. Zunächst wird mit dem euklidischen Algorithmus der größte gemeinsame Teiler von \(47\) und \(42\) bestimmt.

\begin{align*} 47 &= 1 \cdot 42 + {\color{CornflowerBlue} 5} \\[0.5em] 42 &= 8 \cdot 5 + {\color{Orange} 2} \\[0.5em] 5 &= 2 \cdot 2 + {\color{Magenta} 1} \\[0.5em] 2 &= 2 \cdot 1 + 0 \end{align*}

Der größte gemeinsame Teiler \({\color{Magenta}1}\) kann wie üblich an der vorletzten Zeile abgelesen werden. Anwenden des erweiterten euklidischen Algorithmus liefert:

\begin{align*} {\color{Magenta} 1} &= 1 \cdot 5 - 2 \cdot {\color{Orange} 2} \\[0.5em] &= 1 \cdot 5 - 2 \cdot {\color{Orange} \bigl( 42 - 8 \cdot 5 \bigr)} \\[0.5em] &= -2 \cdot 42 + 17 \cdot {\color{CornflowerBlue} 5} \\[0.5em] &= -2 \cdot 42 + 17 \cdot {\color{CornflowerBlue} \bigl( 47 - 1 \cdot 42 \bigr)} \\[0.5em] &= 17 \cdot 47 - 19 \cdot 42 \end{align*}

Aus der erhaltenen Gleichung ergibt sich unmittelbar die folgende Kongruenz:

\begin{align*} \begin{alignedat}{2} 1 &\equiv \underbrace{17 \cdot 47}_{\equiv\ 0} -19 \cdot 42 && \pmod{47} \\[0.5em] &\equiv -19 \cdot 42 && \pmod{47}. \end{alignedat} \end{align*}

Hieraus folgt aufgrund der Definition von Restklassen:

{[1]}_{47} = {[-19 \cdot 42]}_{47} = {[-19]}_{47} \odot {[42]}_{47}.

Da es sich bei \({[-19]}_{47}\) nicht um den Standardvertreter der Restklasse handelt, ist \({[-19]}_{47}\) noch nicht das gesuchte multiplikative Inverse; dieses kann durch Umrechnen in den Standardvertreter der Restklasse jedoch leicht ermittelt werden:

{[-19]}_{47} = {[-19+47]}_{47} = {[28]}_{47}.

Jetzt üben!

Nutze den individuell konfigurierbaren Aufgabengenerator, um unbegrenzt Aufgaben zum Thema Multiplikative Inverse von Restklassen zu erzeugen und zu üben.

Beispiel 2: Satz von Euler

Es soll das multiplikative Inverse von \({[42]}_{47}\) in \(\Z_{47}\) berechnet werden. Da \(42\) und \(47\) teilerfremd sind, gilt aufgrund des Satzes von Euler die folgende Kongruenz:

42^{\varphi(47)} \equiv 42^{46} \equiv 1 \pmod{47}.

Hieraus folgt, dass es sich bei

{[42]}_{47}^{-1} = {[42]}_{47}^{\varphi(47)-1} = {[42]}_{47}^{45}

um das gesuchte multiplikative Inverse von \({[42]}_{47}\) handelt. Dieses kann beispielsweise mit dem Square-and-Multiply-Verfahren über die folgenden Zwischenschritte berechnet werden.

\begin{align*} {[42]}_{47}^{45} &= {[42]}_{47}^{44} \cdot {[42]}_{47} \\[0.5em] {[42]}_{47}^{44} &= {\left( {[42]}_{47}^{22} \right)}^2 \\[0.5em] {[42]}_{47}^{22} &= {\left( {[42]}_{47}^{11} \right)}^2 \\[0.5em] {[42]}_{47}^{11} &= {[42]}_{47}^{10} \cdot {[42]}_{47} \\[0.5em] {[42]}_{47}^{10} &= {\left( {[42]}_{47}^{5} \right)}^2 \\[0.5em] {[42]}_{47}^{5} &= {[42]}_{47}^{4} \cdot {[42]}_{47} \\[0.5em] {[42]}_{47}^{4} &= {\left( {[42]}_{47}^{2} \right)}^2 \\[0.5em] {[42]}_{47}^{2} &= {\left( {[42]}_{47}^{1} \right)}^2 \end{align*}

Ausrechnen von \({[42]}_{47}^{45}\) durch Rückwärtseinsetzen ergibt:

\begin{align*} {[42]}_{47}^{2} &= {[25]}_{47} \\[0.5em] {[42]}_{47}^{4} &= {[14]}_{47} \\[0.5em] {[42]}_{47}^{5} &= {[24]}_{47} \\[0.5em] {[42]}_{47}^{10} &= {[12]}_{47} \\[0.5em] {[42]}_{47}^{11} &= {[34]}_{47} \\[0.5em] {[42]}_{47}^{22} &= {[28]}_{47} \\[0.5em] {[42]}_{47}^{44} &= {[32]}_{47} \\[0.5em] {[42]}_{47}^{45} &= {[28]}_{47} \end{align*}

Für das gesuchte multiplikative Inverse ergibt sich somit:

{[42]}_{47}^{-1} = {[28]}_{47}.