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}.