Inverse Modulo berechnen

21.10.2012, 20:16

OperatorSupierator

Inverse Modulo berechnen

Meine Frage:
Hallo ich habe hier einige Aufgaben und komme nicht weiter:

Ich soll diese Aufgaben ohne Taschenrechner berechnen:

a.) 1/5 mod 13
b.) 1/5 mod 7
c.) 3x2/5 mod 7

Meine Ideen:
Also ich weiss, dass ich mit Inverse arbeiten muss.
Jedoch weiss ich nicht wie ich hier anfangen soll,
zuerst dachte ich es würde einfach z.B bei Aufgabe a, 1/5 bleiben da 13 nicht hineinpasst.

Jedoch habe ich dann mitbekommen, dass die INversen gefragt sind.
Hierbei muss ich ja auch den GGT in Betracht ziehen.

Bitte helft mir weiss nicht weiter unglücklich

21.10.2012, 20:25

Captain Kirk

Auf diesen Beitrag antworten »

Benutze den erweiterten euklidischen Algorithmus.

21.10.2012, 20:37

OperatorSupierator

Auf diesen Beitrag antworten »

also wir sollen versuchen das zu erraten,
den satz vom euler machen wir erst in paar wochen.

wie muss ich denn vorgehen, wenn ich es erraten soll.
bei kleinen zahlen soll dies noch möglich sein, wie bei den aufgaben.
später wirds dann schwieriger, sobald grössere zahlen ins spiel kommen

21.10.2012, 20:43

Captain Kirk

Auf diesen Beitrag antworten »

Dann halt alle zahlen durchprobieren.
Wo ist da das Problem?
Und ich hab keine Ahnung wie du auf den Satz von Euler kommst.

21.10.2012, 20:47

OperatorSupierator

Auf diesen Beitrag antworten »

hehe okay, sry dass sagte mir grad ein anderer studienkollege. Gott

hmm wie geht man denn vor wenn man dass einfache erraten soll?

also 0,2 mod 13
und dann?

21.10.2012, 20:53

Captain Kirk

Auf diesen Beitrag antworten »

Du suchst eine Zahl x mit
$\begin{eqnarray*} x \cdot 5 \equiv 1 \mod 13 \end{eqnarray*}$
Und jetzt alle Kandidaten durchprobieren.

21.10.2012, 21:03

OperatorSupierator

Auf diesen Beitrag antworten »

Das heisst die Zahl die hier gesucht ist wäre 40, da 13 insgesamt 3 mal hineinpasst und Rest 1 wäre.Warum wurde denn aber hinterher in deinem Tipp nur die 5 erwähnt , die Aufgabe war ja 1/2 mod 13?

hat es damit was zu tun dass man a mal a^-1 rechnet?

21.10.2012, 21:11

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

Original von OperatorSupierator
Das heisst die Zahl die hier gesucht ist wäre 40, da 13 insgesamt 3 mal hineinpasst und Rest 1 wäre.Warum wurde denn aber hinterher in deinem Tipp nur die 5 erwähnt , die Aufgabe war ja 1/2 mod 13?

Ich kann dir nicht folgen.
Die Aufgabe war wie du oben geschrieben hast 1/5 mod 13 (Tippfehler?)
40 wäre garantiert nicht die Lösung, du sollst den Representanten mod 13 angeben, also eine Zahl zwischen 0 und 12.

Und $\begin{eqnarray*} 1/x \end{eqnarray*}$ ist in diesem Kontext eine (eine meinen Augen fürchterliche) Schreibweise für das multiplikative Inverse von x, die man sinnvollerweise als $\begin{eqnarray*} x^{-1} \end{eqnarray*}$ bezeichnet.

21.10.2012, 21:20

OperatorSupierator

Auf diesen Beitrag antworten »

Oh man, ich bin ja komplett verwirrt.

Die Aufgabe ist schon korrekt ich meinte 1/5 sry und mit 40 meinte ich eigentlich 8.

Denn 8 wäre der Represetant und ich bin auf 40 gekommen weil ich im Kopf das hier gerechnet habe: 5x8=40

Das heisst: 8 x 5 "KongruenzZeichen" 1 mod 13

Denn somit wäre es 40 "KongruenzZeichen" 1 mod 13

Und die 13 passt insgesamt 3x in die 40 und somit bleibt 1 als Rest übrig.

Ja mein Professor sagte uns auch, dass wir in diesem Kontext die Bruchschreibweise vergessen sollen.

wenn ich jedoch diesen Bruch umschreibe also : 1/5 in -> 5^-1

warum hast du mir dann als tipp diese gleichung gegeben, welche ja die umformung ist:

x * 5 "KongruenzZeichen" 1 mod 13

Da ist ja nur die 5 da und bei mir in der Aufgabe war ja 1/5....nur diesen Teil verstehe ich nicht, sonst ist es klar denke ich

sry Gott

21.10.2012, 21:24

Captain Kirk

Auf diesen Beitrag antworten »

Keine Entschuldigung nötig, es hat sich ja aufgeklärt.
So passts auch.

Aber bitte verwende bei modulo-Rechnung nie wieder Bruchschreibweise.

21.10.2012, 21:42

OperatorSupierator

Auf diesen Beitrag antworten »

Okay danke,

dass heisst

immer wenn ich ein Bruch gegeben habe umwandeln in eine zahl mit einem hoch exponenten

1/5 -> wäre ja 5^-1

und dann einfach in der Rechnung x * 5 "KongruenzZeichen" mod 13

also einfach das hoch weglassen von dem 5^-1

21.10.2012, 21:48

Mystic

Auf diesen Beitrag antworten »

Gegen die Bruchschreibweise hätte ich persönlich nichts einzuwenden... Ich würde das sogar konsequent mit Brüchen so rechnen:

$\begin{eqnarray*} \frac 15 =\frac {1+3\cdot 13}{5}=\frac {40}5=8 \mod 13 \end{eqnarray*}$

Ist aber nur eine andere Form von "Raten", aber bei kleinem Nenner die vermutlich schnellste Methode... Augenzwinkern

21.10.2012, 22:07

Mulder

Auf diesen Beitrag antworten »

Zitat:

Original von OperatorSupierator
immer wenn ich ein Bruch gegeben habe umwandeln in eine zahl mit einem hoch exponenten

1/5 -> wäre ja 5^-1

und dann einfach in der Rechnung x * 5 "KongruenzZeichen" mod 13

also einfach das hoch weglassen von dem 5^-1

Das klingt mir jetzt sehr nach "Vorgehensweise auswendig lernen". Besser wäre aus meiner Sicht aber "Vorgehensweise verstehen".

Gefragt ist nach

$\begin{eqnarray*} 5^{-1} \mod {13} \end{eqnarray*}$

Das heißt: Wir suchen das Inverse zu 5 modulo 13. Das heißt, wir suchen dasjenige Element x, das mit $\begin{eqnarray*} 5 \end{eqnarray*}$ multipliziert gerade 1 modulo 13 ergibt:

$\begin{eqnarray*} x \cdot 5 \equiv 1 \mod {13} \end{eqnarray*}$

Denn dieses "hoch minus 1" ist ja eben eine Schreibweise für das inverse Element bezüglich der Multiplikation. Das x steht hier für das $\begin{eqnarray*} 5^{-1} \end{eqnarray*}$ , das wollen wir ja noch bestimmen. Denn natürlich ist

$\begin{eqnarray*} 5^{-1} \cdot 5 \equiv 1 \mod {13} \end{eqnarray*}$

Augenzwinkern

Also schreiben wir es erst einmal als Unbestimmte x und lösen (bzw. erraten sie in diesem Fall) das dann. Bzw. suchen eben einen Repräsentanten (in ganzzahliger Darstellung), der das Inverse zur 5 bildet.

PS: Ich finde diese Bruchschreibweise prinzipiell auch nicht sonderlich schön in diesem Zusammenhang. Aber wie es scheint, ist das wohl ein wenig Ansichtssache, wenn selbst Mystic das befürwortet. Dann kann es ja so grottendaneben nicht sein. Augenzwinkern

21.10.2012, 22:09

OperatorSupierator

Auf diesen Beitrag antworten »

Boahr Perfekt!!!!!

Ich danke euch allen für die Hilfe smile

21.10.2012, 22:49

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Mulder
PS: Ich finde diese Bruchschreibweise prinzipiell auch nicht sonderlich schön in diesem Zusammenhang. Aber wie es scheint, ist das wohl ein wenig Ansichtssache, wenn selbst Mystic das befürwortet. Dann kann es ja so grottendaneben nicht sein. Augenzwinkern

Zunächst einmal gibt es CAS, wie z.B. Maple, welche mit diesen Brüchen überhaupt kein Problem haben und 1/5 mod 13 würde hier wirklich sofort 8 liefern, d.h., da haben sich schon andere Gedanken über die Sinnhaftigkeit von Brüchen in diesem Zusammenhang gemacht...

Des weiteren gibt es da auch durchaus pragmatische Gründe... Nehmen wir an, eine Übungsaufgabe besteht aus zwei Teilen, wo ein GS einmal in $\begin{eqnarray*} \mathbb Q \end{eqnarray*}$ und einmal in $\begin{eqnarray*} \mathbb{Z}_{13} \end{eqnarray*}$ gelöst werden soll... Muss man nun die Rechnungen von Teil a) für b) wegwerfen? Nein, einfach in der Lösung von a) die Brüche in Elemente von $\begin{eqnarray*} \mathbb{Z}_{13} \end{eqnarray*}$ umschreiben... Augenzwinkern

Neue Frage »

Antworten »

Inverse Modulo berechnen

Verwandte Themen