Multiplikativ Inverse bestimmen (Restklasse)

06.07.2013, 19:16

Tarun

Auf diesen Beitrag antworten »

Multiplikativ Inverse bestimmen (Restklasse)

Aufgabe: Bestimmen Sie das multiplikativ inverse von $\begin{eqnarray*} 11 \in Z_{41} \end{eqnarray*}$

Wir verwenden eigentlich fast nur eine andere Schreibweise, deshalb würde mich erst einmal interessieren ob folgende Schreibweise hiermit gleichgültig ist:

$\begin{eqnarray*} \left[11\right]_{mod41}^{-1} \end{eqnarray*}$

Dann würde mich interessieren wie ich den nun das multiplikativ Inverse bestimme.

Es gilt ja bzgl. Multiplikation

$\begin{eqnarray*} \left[11\right]_{mod41}^{-1} \end{eqnarray*}$ * b = 1

<-> b=1 durch $\begin{eqnarray*} \left[11\right]_{mod41}^{-1} \end{eqnarray*}$

Ist der Ansatz richtig ? Wie geht es weiter ?

06.07.2013, 19:21

watcher

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Wir verwenden eigentlich fast nur eine andere Schreibweise, deshalb würde mich erst einmal interessieren ob folgende Schreibweise hiermit gleichgültig ist: $\begin{eqnarray*} \left[11\right]_{mod41}^{-1} \end{eqnarray*}$

Ja das ist gleichbedeutend.

Zitat:

$\begin{eqnarray*} \left[11\right]_{mod41}^{-1} \end{eqnarray*}$ * b = 1 <-> b=1 durch $\begin{eqnarray*} \left[11\right]_{mod41}^{-1} \end{eqnarray*}$ Ist der Ansatz richtig ? Wie geht es weiter ?

Ich seh hier nicht wirklich einen Ansatz.
Der erweiterte euklidische Algorithmus ist nützlich.

06.07.2013, 19:47

Tarun

Auf diesen Beitrag antworten »

Komisch, den hatten wir aber nicht. Bzw. ist der Name nie gefallen.

06.07.2013, 19:52

Tarun

Auf diesen Beitrag antworten »

Ich habe mir jetzt kurz den Algorithmus angeschaut. Dort wird aber nicht mit Inversen gerechnet, sondern nur mit z.b. 5 modulo 48... also ohne ^-1

Wie spricht man eigentlich mathematisch ausgedrückt meine vorgegebene Restklasse aus ?

06.07.2013, 20:02

watcher

Auf diesen Beitrag antworten »

Der Wikipedia-Artikel zum erweiterten euklidischen Algorithmus z.B. weist ausdrücklich (und verlinkt) darauf hin, dass das Bilden von Inversen ein wesentliches Einsatzgebeit des EEA ist.

Wenn der Algorithmus noch nicht bekannt ist hilft nur Probieren.
Falls der Satz von Euler-Fermat bekannt ist könnte man noch auf die Idee kommen $\begin{eqnarray*} 11^{39} \mod 41 \end{eqnarray*}$ zu berechnen

Zitat:

Wie spricht man eigentlich mathematisch ausgedrückt meine vorgegebene Restklasse aus ?

Also:

Zitat:

$\begin{eqnarray*} \left[11\right]_{mod41}^{-1} \end{eqnarray*}$

Das (multiplikativ) Inverse von 11 modulo 41 würd ich vorschlagen.

06.07.2013, 20:16

Tarun

Auf diesen Beitrag antworten »

Kannst du bitte ein kurzes Beispiel in meiner verwendeten Schreibweise darstellen?

Anzeige

06.07.2013, 20:20

watcher

Auf diesen Beitrag antworten »

Ein kurzes Beispiel wofür?

06.07.2013, 20:23

Tarun

Auf diesen Beitrag antworten »

Ob du bitte das multiplikativ Inverse einer Restklasse in dieser von uns genutzen Schreibweise bestimmen kannst, damit ich sehe was zu tun ist.

Ich lese überall, dass ein Element a in IZ_m ein multiplikatives inverses <-> a * x = 1 mod m

06.07.2013, 20:26

watcher

Auf diesen Beitrag antworten »

Und welche der vorgestellten Methoden ist gewünscht?

Zitat:

Ich lese überall, dass ein Element a in IZ_m ein multiplikatives inverses <-> a * x = 1 mod m

Das ist im Wesentlichen ja auch die Def.
Wo ist eigentlich überall?

06.07.2013, 20:32

Tarun

Auf diesen Beitrag antworten »

Schöne Frage. Ich meine im Internet. Ein Passendes Beispiel finde ich nicht. Also ich habe zwar eine passende Seite gefunden, aber weis nicht ob das bezogen auf mein Beispiel der richtige Ansatz ist.

Fängt man wie folgt an:

41= 3*11 + 8

11=1*8 +2

8= 4* 2

... Das geht genau auf wenn das richtig sein sollte. Ich weiss aber gar nicht was ich hier gerade tue.^^ Wird hier mit multiplikativ inverses dasselbe gemeint wie a*b=e, wobei b das multiplikative von a ist ?

?

06.07.2013, 20:47

watcher

Auf diesen Beitrag antworten »

Der erweiterte euklidische Algorithmus solls also sein.

Zitat:

Fängt man wie folgt an: 41= 3*11 + 8 11=1*8 +2 8= 4* 2

Vorletzte Zeile ist falsch.
Und das ist nur der euklidische Algorithmus noch nicht der erweiterte.
Genauere Infos: Wiki

Ein kleines Beispiel:
Gesucht: $\begin{eqnarray*} [3]^{-1}_{mod 17} \end{eqnarray*}$
17= 5*3+2
3= 2+1

Auflösen der letzen Gleichung nach 1:
1=3-2
Auflösen der nächsten Gleichung nach 2 (dem Rest der Division):
2=17-5*3
Einsetzen:
1=3-(17-5*3)
=-17 +6*3
(wir wollen ja eine Darstellung a*17+b*3, daher beim Ausmultiplizieren 3 und 17 "wie Variablen" behandeln.)
Das ergibt:
$\begin{eqnarray*} 1\equiv 6\cdot 3 \mod 17 \end{eqnarray*}$
oder anders geschrieben:
$\begin{eqnarray*} [1]_{mod 17}=[6]_{mod17}[3]_{mod17} \end{eqnarray*}$

Zitat:

mit multiplikativ inverses dasselbe gemeint wie a*b=e, wobei b das multiplikative von a ist ?

Ja du bist hier in einer multiplikativen gruppe mit e=1.

06.07.2013, 20:48

alterHund

Auf diesen Beitrag antworten »

also etwas besseres als Probieren gibt es schon

06.07.2013, 21:43

Tarun

Auf diesen Beitrag antworten »

Zitat:

Original von watcher

Ein kleines Beispiel:
Gesucht: $\begin{eqnarray*} [3]^{-1}_{mod 17} \end{eqnarray*}$
17= 5*3+2
3= 2+1

Auflösen der letzen Gleichung nach 1:
1=3-2
Auflösen der nächsten Gleichung nach 2 (dem Rest der Division):
2=17-5*3
Einsetzen:
1=3-(17-5*3)
=-17 +6*3
(wir wollen ja eine Darstellung a*17+b*3, daher beim Ausmultiplizieren 3 und 17 "wie Variablen" behandeln.)
Das ergibt:
$\begin{eqnarray*} 1\equiv 6\cdot 3 \mod 17 \end{eqnarray*}$
oder anders geschrieben:
$\begin{eqnarray*} [1]_{mod 17}=[6]_{mod17}[3]_{mod17} \end{eqnarray*}$

Zitat:

mit multiplikativ inverses dasselbe gemeint wie a*b=e, wobei b das multiplikative von a ist ?

Ja du bist hier in einer multiplikativen gruppe mit e=1.

Ich hab bei einer anderen Qulle gelesen, das man von der vorletzten Zeile rückwärst ,,rechnen" tut. Ist das hier eine Ausnahme, da es sich nur um insgesamt zwei Zeilen handeln tut? Oder worin liegt der Grund ?

06.07.2013, 21:45

watcher

Auf diesen Beitrag antworten »

Ich rechne hier rückwärts, genauso wie deine Quelle.

P.S. Sätze mit "tut" sind schmerzhaft zu lesen.

06.07.2013, 21:52

Turan

Auf diesen Beitrag antworten »

Zitat:

Original von watcher
Ich rechne hier rückwärts, genauso wie deine Quelle.

P.S. Sätze mit "tut" sind schmerzhaft zu lesen.

Ich hab es beinahe verstanden. Das einzige Problem liegt, dass ich beim Ausmultiplizieren der Klammer irgendetwas falsch mach. Es wird folgendes angemerkt:

"Beachte, dass dabei zwar alle aufretenden Klammern ausmultipliziert, nicht aber alle Produkte ausmultipliziert werden!"

Das verstehe ich nicht so ganz mit den Produkten.

06.07.2013, 21:55

watcher

Auf diesen Beitrag antworten »

Ich zitier mich mal selbst:

Zitat:

wir wollen ja eine Darstellung a*17+b*3, daher beim Ausmultiplizieren 3 und 17 "wie Variablen" behandeln.

06.07.2013, 22:05

Turan

Auf diesen Beitrag antworten »

Wenn ich sie variablen behandele komme ich leider nicht auf diese Zusammenfassung für:

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

Wie komm ich auf denselben Term?

06.07.2013, 22:08

watcher

Auf diesen Beitrag antworten »

Zitat:

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

Das ist auch falsch und ich hab keine Ahnung wo du die linke Seite her hast.

06.07.2013, 22:15

Tarun

Auf diesen Beitrag antworten »

Also dieser Term war falsch dargestellt von mir. Tut mir leid. Es soll nämlich

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

heißen. (Das ist ein Term von einer anderen ähnlichen Aufgabe)

06.07.2013, 22:24

watcher

Auf diesen Beitrag antworten »

Distributivgesetz:

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

06.07.2013, 22:46

Tarun

Auf diesen Beitrag antworten »

Danke, ich bin jetzt sicherer hier bezüglich. Mich würde noch folgendes interessieren. Was wird im folgenden gemacht:

1. 2*48-19*5=1
2. -19*5 mod 48 = 1
3. 29*5mod 48=1

Also vom 1.-2. Schritt verstehe ich nicht weshalb die 2 verschwindet. Kann man das eventuell in dieser Schreibweise darstellen: [2*48-19*5]mod48=1 ? Oder wie sollte das in unserer genutzen Schreibweise lauten?

Außerdem ist mir nicht der 2.-3. Schritt verständlich. Könntest du mir bitte da nochmals helfen.

07.07.2013, 00:43

turan

Auf diesen Beitrag antworten »

Kann man das eventuell irgendwie in unserer genutzen Schreibweise umschreiben?

Also z.b. [14+4]mod7=[4mod]mod7

07.07.2013, 08:18

watcher

Auf diesen Beitrag antworten »

Es ist $\begin{eqnarray*} [a+b]=[a]+[b] \mod n \end{eqnarray*}$
ebenso für * statt +.

Ferner gilt: $\begin{eqnarray*} [kn]=[0] \mod n \end{eqnarray*}$ für alle ganzen Zahlen k.

07.07.2013, 11:48

Tarun

Auf diesen Beitrag antworten »

Also kann ich mir das vorgegebene mod 48 sofort hinzufügen? Also die erste Zeile bereits umschreiben zu:
[2*48-19*5]mod48=1 bzw. [2*48]mod48+[-19*5]mod48=[-19*5]mod48=[-95]mod48 (Darf ich das hier zusammenfassen?) Den eigentlich wird hier beim Beispiel weitergerechnet mit:

9*5mod 48=1
29*5mod 48=1

07.07.2013, 13:45

Tarun

Auf diesen Beitrag antworten »

Beim Post über mir meine ich -19, nicht 9.

Ich vermute Mal, dass ich nicht zusammenfassen darf, aber weshalb?
Also ich würde jetzt vom Anfang aus, wie folgt zusammenfassen, sofern ich definitiv nicht zusammenfassen darf, abgesehen vom Ausklammern:

2*48-19*5=1
[2*48]mod48+[-19*5]mod48=[1]mod48
[-19]mod48*[5]mod48=[1]mod48
[29]mod48*[5]mod48=[1]mod48 <->
([5]mod48)^-1=29

So komme ich auf das richtige Ergebnis. Ist das richtig so? Wenn ja würde mich noch interessieren wieso ich nicht -19*5 zusammenfassen darf, denn da komm ich auf ein falsches Ergebnis.

07.07.2013, 13:54

Tarun

Auf diesen Beitrag antworten »

Ah, stimmt ich darf ja gar nicht zusammenfassen, da ich von [5]mod48 die Inverse bestimmen soll.

Ich denke ich habs jetzt! Vielen dank für deine so große Mühe!

07.07.2013, 17:09

Turan

Auf diesen Beitrag antworten »

RE: Multiplikativ Inverse bestimmen (Restklasse)
Hallo, ich bin es noch einmal. Ich hab es jetzt verstanden, bin jedoch auf ein Problem gestoßen:

[quote]Original von Tarun
Aufgabe: Bestimmen Sie das multiplikativ inverse von $\begin{eqnarray*} 11 \in Z_{41} \end{eqnarray*}$
/quote]

Meine Rechnung sieht wie folgt aus: Da ggT(41,11)=1 ist multiplikativ inverses von [11]mod41 vorhanden.

41=3*11+8
11=1*8+3
8=2*3+2
3=1*2+1
2=2*1+0

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

Hier ist mein Problem, wenn ich nun die zweie Zeile nach den Rest 3 auflöse muss ich das ja einsetzen in meine ,,Rückrechnung". Da sind zwei dreien vorhanden. Muss ich somit beide ersetzen durch ,,11-1*8" ? Also was wäre richtig:

(11-1*8)*(11-1*8)-1*8 oder 3*(11-1*8)-1*8

07.07.2013, 18:19

ollie3

Auf diesen Beitrag antworten »

RE: Multiplikativ Inverse bestimmen (Restklasse)
hallo,
hatte das hier gestern mitverfolgt und übernehme mal:
richtig ist das zweite:
1=3*(11-1*8)-1*8
=3*11-4*8
Jetzt kann man für 8 wieder 41 - 3*11 einsetzen, neu zusammenfassen
und kommt dann zum ziel.
gruss ollie3

07.07.2013, 19:43

Turan

Auf diesen Beitrag antworten »

Danke, ich hab es raus. smile

smile

Mich würde jetzt eine wichtige Frage interessieren. Wieso ersetzt ich die andere drei nicht? Also das kam mir schon auffällig vor, aber mir ist nicht genau im klaren weshalb.

07.07.2013, 20:27

Turan

Auf diesen Beitrag antworten »

Mich würde außerdem interessieren wieso ich nicht mit dem Euklidischen Algo. ([1]mod5)^-1 berechnen kann.

08.07.2013, 16:15

watcher

Auf diesen Beitrag antworten »

Zitat:

Wieso ersetzt ich die andere drei nicht? Also das kam mir schon auffällig vor, aber mir ist nicht genau im klaren weshalb.

Es wird immer nur eine Zahl erstetzt, und zwar der rest in der jeweiligen gleichung des eukl. Alg. Und die eine 3 hier ist nur ein Faktor.

Zitat:

Mich würde außerdem interessieren wieso ich nicht mit dem Euklidischen Algo. ([1]mod5)^-1 berechnen kann.

Mich würde interessieren wieso du das Inverse des neutralen Elements berechnen willst?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »