Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Multiplikatives Inverses finden (?)

Multiplikatives Inverses finden (?)

Universität / Fachhochschule

Tags: Diskrete Mathematik, Multiplikatives Inverses

Naico aktiv_icon

19:47 Uhr, 14.01.2010

Guten Abend,

ich habe mir einer Aufgabe hier folgendes Problem, ich soll das multiplikative Inverse finden.

Mir ist klar, dass wenn der ggT

= 1

ist, dann gibt es ein inverses, wenn es ungleich 1 ist, dann nicht.

Jetzt habe ich hier diese Aufgabe und weiss nur nicht, wie ich an das Inverse rankomme:

bestimme das multi. Inverse von

16 \in Z 17 ...

. dass bei dem euklidischen algo. da eine 1 rauskommt war klar ;-)

Nur wie mache ich weiter? Danke im voraus!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

michaL aktiv_icon

20:00 Uhr, 14.01.2010

Hallo,

es gilt doch

16 \equiv - 1

mod 17. Wenn du ein multiplikatives Inverses von -1 kennst, kennst du auch eins von 16.

Mfg Michael

Naico aktiv_icon

20:03 Uhr, 14.01.2010

Moin,

das bringt mich irgendwie nicht weiter

\frac{:}{}

michaL aktiv_icon

20:10 Uhr, 14.01.2010

Hallo,

viel "die Lösung in Zusammenarbeit mit anderen erstellen" ist nicht mehr drin, wenn es nur um das Inverse geht.

(- 1) \cdot (- 1) = 1

darf man als Student aber schon ruhig wissen.
Alternativ kannst du auch mal 16*16 berechnen.

Sollte es darum gehen, das Inverse mit dem euklidischen Algorithmus zu finden, hättest du deine Frage ruhig präziser stellen sollen.
Gib dann noch mal Bescheid.

Mfg Michael

Naico aktiv_icon

20:12 Uhr, 14.01.2010

Nunja, uns wurde halt gesagt, wir sollen das inverse mit Hilfe des euklidischen Algorithmus, durch Rückwärtseinsetzen, bestimmen.

Nur stehe ich gerade halt auf dem Schlauch, wie ich da ran komme

: - (

michaL aktiv_icon

20:32 Uhr, 14.01.2010

Hallo,

hab ich doch geahnt.

Machen wir mal bei 16 und 17 den (erweiterten) euklidischen Algorithmus und finden dann

u

und

v

, sodass

16 u + 17 v = 1

.

17=1*16 Rest 1
16=16*1 Rest 0

Also ist der vorletzte Rest der ggT.

Offenbar gilt also

17 = 1 \cdot 16 + ggT

, d.h.

1 = ggT = 1 \cdot 17 + (- 1) \cdot 16

.
Betrachtest du die letzte Gleichung modulo 17, heißt sie einfach

(- 1) \cdot 16 = 1

mod 17, d.h. -1 ist multiplikatives Inverses von 16 modulo 17. Es gilt außerdem -1=16=33=... mod 17.

Mfg Michael

PS: An diesem Beispiel ist der euklidische Algorithmus nicht gut zu erkennen, zu wenig Tiefe.

Naico aktiv_icon

20:34 Uhr, 14.01.2010

Danke MichaL,

ich hab noch mehr Aufgaben, ich brauch nur eine um zu verstehen, wie ich das nun am geschicktesten Anwende, die Aufgaben sind aber alle so in dem Ausmaß...

Ich versuchs mal mit den folgenden, vielen Dank!

Naico aktiv_icon

20:48 Uhr, 14.01.2010

Hiermit darf ich nun weitermachen -

3 \in Z 17

und ich soll herausfinden ob

73 \in Z 800

invertierbar ist

. .

hagman aktiv_icon

20:58 Uhr, 14.01.2010

Invertieren von

3 \in ℤ_{17}

geht übrigens schon wieder leichter durch Raten als durch den Euklidischen Algorithmus. Kannst du ein Vielfaches von 3 finden, das nur eins mehr ist als ein Vielfaches von

17

(also als eine der Zahlen

17, 34, 51, ...)

?
Mit dem geratenen Ergebnis kannst du weinigstens dei Euklid-Ergebnis kontrollieren.

Es sollte bekannt sein, dass die Invertierbarkeit im Zusammenhang mit Teilerfremdheiot steht, oder?

800 = 2^{5} \cdot 5^{2}

Naico aktiv_icon

21:07 Uhr, 14.01.2010

Also für das Invertierbare von

73 \in Z 800

habe ich

753

raus!

753

ist das gesuchte Inverse. Lt. meiner Rechnung...

michaL aktiv_icon

23:01 Uhr, 14.01.2010

Hallo,

ich nicht.

73 \cdot 753 \equiv 569

mod 800 bei mir (für solche Sachen ist ein Modulorechner echt ne Hilfe).
Aber an diesem Beispiel kommt man gut mit dem Euklidischen Algorithmus vorwärts (modulo Rechenfehlern):

800 = 10*73 R 70
73 = 1*70 R 3
70 = 23*3 R 1
Letzte Zeile können wir uns sparen, der ggT ist 1, infolge dessen ist 73 modulo 800 invertierbar.

Aus der letzten Zeile folgt:

1 = 1 \cdot 70 - 23 \cdot 3

= 1 \cdot 70 - 23 (1 \cdot 73 - 1 \cdot 70) = 24 \cdot 70 - 23 \cdot 73

= 24 (1 \cdot 800 - 10 \cdot 73) - 23 \cdot 73 = 24 \cdot 800 - 263 \cdot 73

Also gilt

1 = 24 \cdot 800 + (- 263) \cdot 73

, damit ist in

ℤ_{800}

das Inverse von 73 eben -263 oder (falls dir das lieber ist)

537 = 800 - 263

.

Mfg Michael

Avrat aktiv_icon

17:18 Uhr, 18.04.2011

Hallo,

da ich zum ersten Mal in diesem Forum bin und nicht genau weiß, wo genau ich lande, schicke ich voraus, daß ich kein Mathematik-(sondern Philosophie)-Student bin, es mir um die Berechnung des multiplikativen Inversen geht und ich zuletzt auf einer Seite dieses Forums war, auf der es genau um dieses multiplikative Inverse ging und Naico und michaL den für mich vielversprechendsten Lösungsansatz diskutierten.
Ich habe bisher herausgefunden, daß man offenbar mit dem erweiterten Euklidschen Algorithmus dieses Inverse berechnen kann. Wie dieser Algorithmus angewendet wird, habe ich inzwischen begriffen. Mein konkreter Fall: das multiplikative Inverse von

37457

zum Modul

2147483647

berechnen. Zunächst das ggT mit dem Algorithmus:

2147483647 = 37457

57331 + 36380

37457 = 36380

1 + 1077

36380 = 1077

33 + 839

1077 = 839

1 + 238

839 = 238

3 + 125

238 = 125

1 + 113

125 = 113

1 + 12

113 = 12

9 + 5

12 = 5

2 + 2

5 = 2

2 + 1

Damit ist formal bewiesen, daß

37457

und

2147483647

teilerfremd sind – aber das wußte ich vorher schon, denn (nicht ganz) zufälligerweise ist

2147483647

eine Primzahl. Der einzige Grund, warum ich mir diesen Algorithmus überhaupt genauer angesehen habe, war, daß auf mehreren Internet-Seiten (und in mehreren Google-Büchern) behauptet wird, als "Nebeneffekt" des erweiterten Euklidschen Alsgorihtmus

(e . E . A .)

erhielte man auch das multiplikative Inverse.
Und genau das ist es, was mich nach drei Tagen Problemwälzen beinahe zur Verzweiflung treibt. Denn ich habe einerseits das Gefühl, nicht weit entfernt von der Lösung meines Problems zu sein, kann aber andererseits so gar nicht erkennen, inwiefern man aus den Rechenschritten oben das multiplikative Inverse (künftig

m . I .)

ableiten kann.
Auf mehreren Seiten habe ich sinngemäß ferner gelesen, daß die Formel

ggT(a,

b) =

+

yb

bei der Berechnung eine Rolle spielt; es ist mir aber in keiner Weise klar, in welcher Beziehung xa

+

yb zum

e . E . A

. steht. Sie scheint eine Rolle bei dem zu spielen, was Naico "Rückwärtseinsetzen" genannt hat, und was der eigentliche Lösungsweg ist (den man wirklich nicht als "Nebeneffekt" des

e . E . A

. bezeichnen kann, sondern als eigenständige und auch nicht-triviale Operation ansehen muß). Der auf der besagten Seite diskutierte Fall war simpler, nämlich

800 = 73

10 + 70

73 = 70

1 + 3

70 = 3

23 + 1

Dazu schrieb michaL:

"Aus der letzten Zeile folgt:

1 = 1

70 - 23

· 3

= 1

70 - 23 (1

73 - 1

70)

= 24 (1

800 - 10

73) - 23

73 = 24

800 - 263

73

"

An dieser (entscheidenden) Stelle habe ich mich festgefahren. Mir ist natürlich klar, daß es hier genau um dieses Rückwärtseinsetzen geht und daß besagte Formel xa

+

yb dabei offenbar die entscheidende Rolle spielt. Mir ist aber weder der theoretische Hintergrund für diese Formel noch ihre Anwendung auf meinen anfangs geschilderten Fall, also die Berechnung des

m . I

. von

37457 (= x)

zum Modul

2147483647

klar, so daß gilt:

37457

x \equiv 1 mod 2147483647

Bin für jeden Hinweis sehr dankbar.

Walter

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

879639

708821

	Status: nicht eingeloggt	Noch nicht registriert?