Multiplikative Inverse mit erweitertem euklidischen Algorithmus

15.09.2016, 20:48

Adramelec

Multiplikative Inverse mit erweitertem euklidischen Algorithmus

Hallo!

Ich soll das multiplikative Inverse von 7 in $\begin{eqnarray*} Z_{26} \end{eqnarray*}$ berechnen.

Als erstes führe ich folgendes durch:
26 = 3*7+5
7 = 1*5 +2
5 = 2*2 +1
2 = 2*1 +0

Dadurch sehe ich Teilerfremdheit und ein multiplikatives Inverse kann gefunden werden.

Nun beginnt der für mich unklare Part..

Ich forme vom euklidischen algorithmus die 2 zeilen:
26 = 3*7+5
und
5 = 2*2 +1

um. So das ich erhalte:

5 = 26 - (3*7)
1 = 5 - (2*2)

Nun setze ich in
1 = 5 - (2*2) die gleichung von oben ein:
1 = 26 - (3*7) - (2*2)

Aber nun weiß ich gar nicht mehr weiter. Ich würde nun anhand des Probe beispiel folgendes raten das ich tun muss:

Ich weiß ja nun das wenn ich 26 - (3*7) - (2*2) ausrechne 1 rauskommt.
Nun entferne ich 26 (den Wert nehme ich von $\begin{eqnarray*} Z_{26} \end{eqnarray*}$ ) und nun bleibt übrig: 17.

Bedeutet das, dass:
17 * 1/7 mein multiplikatives Inverse ist?

(sorry falls ich irgendwo hier komplett falsch abgebogen ist. Danke schon mal voraus smile

)

15.09.2016, 22:27

Mathema

Auf diesen Beitrag antworten »

Ich kann dir nicht folgen. Es ist:

$\begin{eqnarray*} 1=5-2\cdot 2 =5-2(7-1\cdot 5)=-2\cdot 7 + 3 \cdot 5 =-2 \cdot 7+3(26-3\cdot 7 )=3\cdot 26 -11 \cdot 7 \end{eqnarray*}$

Somit gilt:

$\begin{eqnarray*} -11\cdot 7 \pmod{26} = 1 \end{eqnarray*}$

Addieren wir noch $\begin{eqnarray*} 26\cdot 7 \end{eqnarray*}$ erhalten wir:

$\begin{eqnarray*} 15\cdot 7 \pmod{26}=1 \end{eqnarray*}$

Und somit $\begin{eqnarray*} 7^{-1} \pmod{26}=15 \end{eqnarray*}$

16.09.2016, 10:52

Adramelec

Auf diesen Beitrag antworten »

Danke das hat mir sehr geholfen.

Ich hab nun ein zweites Beispiel. Prinzipiell versteh ich (so glaube ich) nun die Systematik. Aber irgendwo hab ich wohl noch einen Fehler drinnen und ich finde ihn nicht.

a) Finde das multiplikative Inverse a=19 und m=999
Erstmal den Algorithmus anwenden: $\begin{eqnarray*} 999 = 52 * 19 + 11 19 = 1 * 11 + 8 11 = 1 * 8 + 3 8 = 2 * 3 + 2 3 = 1 * 2 + 1 2 = 2 * 1 + 0 \end{eqnarray*}$
Gut. Nun das ganze "rückwärts".
$\begin{eqnarray*} 1 = 3 -1 * 2 = 3 -1 * (8 -2 * 3) = -1 * 8 + 2 * 3 = -1 * 8 + 2 * (11 -1 * 8) = 2 * 11 - 3 * 8 = 2 * 11 - 3 * (19 -1 * 11) = -3 * 19 + 5 * 11 = -3 * 19 + 5 * (999 -52 * 19) = 5 * 999 -263 * 19 \end{eqnarray*}$
Nun sollte ja folgendes stimmen:
-263*19 mod 999 = 1. Stimmt aber leider nicht.

Wo mach ich den Fehler?

16.09.2016, 11:53

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Adramelec
Gut. Nun das ganze "rückwärts".

1 = 3 -1 * 2
= 3 -1 * (8 -2 * 3)
= -1 * 8 + 2 * 3

Hier ist der Fehler (zumindest der erste - den Rest hab ich dann nicht mehr angeschaut):

= -1 * 8 + 3 * 3

16.09.2016, 13:50

Adramelec

Auf diesen Beitrag antworten »

Danke für den Hinweis, habs nochmal gerechnet. Stimmt noch immer nicht.
Offensichtlich bin ich komplett blind. verwirrt

$\begin{eqnarray*} 1 = 3 -1*2 = 3 -1*(8 -2*3) = 1*8+3*3 = 1*8 + 3*(11-1*8) = 3*11 -2*8 = 3*11 -2 *(19-1*11) = -2*19 + 5*11 = -2*19 + 5*(999-52*19) = 5*999 - 262*19 \end{eqnarray*}$

Danke smile

16.09.2016, 14:33

HAL 9000

Auf diesen Beitrag antworten »

Dieselbe Zeile, aber anderer Fehler!!!

= -1 * 8 + 3 * 3

Wenn du mit derselben Konzentration weitermachst, sitzen wir heute noch den ganzen Tag dran. unglücklich

Vorschlag: Bei jeder, wirklich jeder Zeile rechnest du von nun an zur Kontrolle nach, ob immer noch 1 rauskommt. Forum Kloppe

17.09.2016, 13:21

Adramelec

Auf diesen Beitrag antworten »

Danke, nachdem ich nun heute frisch an die Sache rangegangen bin, gings mir damit besser und ich konnte es lösen.

(Danke auch für den Tipp in jeder Zeile zu prüfen ob 1 rauskommt. Im Nachhinein sehr offensichtlich, aber gestern wäre ich nicht auf die Idee gekommen)

Danke! Freude

Neue Frage »

Antworten »

Multiplikative Inverse mit erweitertem euklidischen Algorithmus

Verwandte Themen