Inverses Element - Restklassenring

06.02.2013, 22:23

x^2+1<0

Inverses Element - Restklassenring

Meine Frage:
Wie finde ich schnell das inverse Element im Restklassenring?

Meine Ideen:
Ich finde sehr schnell die Einheiten im Restklassenring,
die inverseren Elementa dazu jedoch nur Mühselig mit
$\begin{eqnarray*} <br /> Inverses Element * Einheit \equiv 1 ~ ~ ~ (mod~ n)<br /> \end{eqnarray*}$

also die vielfachen der Einheit auf Teilbarkeit mit n prüfen und gucken ob Rest 1 rauskommt. Sehr unhandlich...
Gibt's da was effizienteres?

wikipedia und die Suchfunktion waren nicht hilfreich

06.02.2013, 23:09

10001000Nick1

Auf diesen Beitrag antworten »

Ich mach mal ein Beispiel, wie ich das berechne:

Wir suchen das Inverse von 37 in $\begin{eqnarray*} \mathbb{Z}/91\mathbb{Z}. \end{eqnarray*}$
Man berechnet mithilfe des erweiterten Euklidischen Algorithmus $\begin{eqnarray*} ggT(91,37): \end{eqnarray*}$

$\begin{eqnarray*} 91=2\cdot37+17 \end{eqnarray*}$
$\begin{eqnarray*} 37=2\cdot17+3 \end{eqnarray*}$
$\begin{eqnarray*} 17=5\cdot3+2 \end{eqnarray*}$
$\begin{eqnarray*} 3=1\cdot2+1 \end{eqnarray*}$
$\begin{eqnarray*} 2=2\cdot1+0 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow ggT(91,37)=1\Rightarrow \end{eqnarray*}$ 37 ist in $\begin{eqnarray*} \mathbb{Z}/91\mathbb{Z} \end{eqnarray*}$ eine Einheit.

Mithilfe des erweiterten Euklidischen Algorithmus berechnet man jetzt:
$\begin{eqnarray*} 1=3-1\cdot2 \end{eqnarray*}$
$\begin{eqnarray*} =3-1\cdot(17-5\cdot3)=6\cdot3-1\cdot17 \end{eqnarray*}$
$\begin{eqnarray*} =6\cdot(37-2\cdot17)-1\cdot17=6\cdot37-13\cdot17 \end{eqnarray*}$
$\begin{eqnarray*} =6\cdot37-13\cdot(91-2\cdot37)=32\cdot37-13\cdot91 \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \overline{1}\equiv \overline{32}\cdot\overline{37}-\overline{13}\cdot\overline{91}\equiv \overline{32}\cdot\overline{37}~~~(mod~91) \end{eqnarray*}$

Also ist $\begin{eqnarray*} \overline{32} \end{eqnarray*}$ das multiplikative Inverse von $\begin{eqnarray*} \overline{37} \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb{Z}/91\mathbb{Z}. \end{eqnarray*}$

Ich hoffe, das hat dir jetzt geholfen. smile