Aufgaben
Aufgaben zum multiplikativen Inversen von Restklassen
Der interaktive Aufgabengenerator zum Thema Multiplikative Inverse von Restklassen erstellt dir eine unbegrenzte Anzahl an individuell anpassbaren Aufgaben und unterstützt dich dabei, diese zu bearbeiten und zu lösen – unter anderem durch ausführliche und verständliche Musterlösungen. Darüber hinaus ist dieselbe Unterstützung auch für deine eigenen Aufgaben verfügbar.
Aufgabe 1 von 2
Bestimme das multiplikative Inverse von \([23]_{42}\) in \({\Z}_{42}\) mithilfe des erweiterten euklidischen Algorithmus.
Zum Bestimmen des multiplikativen Inversen von \(23\) in \(\Z_{42}\) muss mit dem euklidischen Algorithmus zunächst der größte gemeinsame Teiler von \(42\) und \(23\) berechnet werden.
\[\begin{align*}
42 &= 1 \cdot 23 + 19 \\[0.5em]
23 &= 1 \cdot 19 + 4 \\[0.5em]
19 &= 4 \cdot 4 + 3 \\[0.5em]
4 &= 1 \cdot 3 + 1 \\[0.5em]
3 &= 3 \cdot 1 + 0
\end{align*}\]
Der größte gemeinsame Teiler \(1\) kann wie üblich an der vorletzten Zeile abgelesen werden. Da \(42\) und \(23\) folglich teilerfremd sind, kann das gesuchte multiplikative Inverse durch Rückwärtseinsetzen gefunden werden.
\[\begin{align*}
1 &=1\cdot4-1\cdot3 \\[0.5em]
&=1\cdot4-1\cdot(19-4\cdot4) \\[0.5em]
&=-1\cdot19+5\cdot4 \\[0.5em]
&=-1\cdot19+5\cdot(23-1\cdot19) \\[0.5em]
&=5\cdot23-6\cdot19 \\[0.5em]
&=5\cdot23-6\cdot(42-1\cdot23) \\[0.5em]
&=-6\cdot42+11\cdot23
\end{align*}\]
Aus dieser Gleichheit kann insbesondere die folgende Kongruenz abgelesen werden:
\[\begin{align*}
1 &\equiv \underbrace{-6 \cdot 42}_{\equiv 0}+11 \cdot 23 \pmod{42} \\[0.5em]
&\equiv 11 \cdot 23 \pmod{42}
\end{align*}\]
Bei \(x=11\) handelt es sich um das gesuchte multiplikative Inverse von \(23\) in \(\Z_{42}\).
