FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Mathematik

Multiplikative Inverse?

Multiplikative Inverse? 2006-12-03 00:05
Anonymer User
hat jemand lust mir noch mal schritt für schritt einfach zu erklären wie man auf des inverse kommt?

mir ist aufgefallen, dass ich die dinge sehr gut verstehe wenn ihr sie mir hier erklärt. davon würde ich gerne wieder gebrauch machen :)

ich bräuchte nur mal jemand der mir in diesem ganze wirrwarr möglichst einfach erklärt wie man das inverse bei günstigen zahlen schon so ohne rechnen erkennt, und wie man sonst am besten vorgeht.

was sich so in eurem kopf abspielt wenn ihr zum beispiel das multiplikative inverse von 2 in Z_17 bestimmen sollt?

vielen dank schonmal.

(edit fal: Topictitel)

Re: Multiplikative Inverse? 2006-12-03 00:14
UncleOwen
Bei so kleinen Zahlen? Ausprobieren ;)

Ne, ernsthaft. Erstmal erweiterten euklidischen Algorithmus auf 17 und 2 anwenden:

17 = 8*2 + 1
2 = 2*1 + 0

Erste Feststellung: 17 und 2 sind teilerfremd, also gibt es ein Inverses (ansonsten gaebe es keins).
Zweite Feststellung: Wir koennen die obere Gleichung so Umstellen, dass wir eine Darstellung der 1 als Linearkombination von 2 und 17 erhalten (im allgemeinen setzt man jetzt rueckwaerts jeweils in die Gleichung da drueber ein):

1 = 17 + (-8)*2.

Also sind -8 und 2 (genauergesagt: die Kongruenzklassen, in denen -8 und 2 enthalten sind) in Z_17 zueinander invers. Da wir aber im allgemeinen eine Zahl zwischen 1 und 16 suchen, ist nicht -8 das gesuchte Inverse, sondern 17-8=9.

Re: Multiplikative Inverse? 2006-12-03 15:34
Anonymer User
kann man nicht sagen, man sucht die zahl, die mit 2 multipliziert 18 ergibt, weil dann der rest zu 17 gleich 1 ist. also 2 * 8 = 1 in Z_17 ?

Re: Multiplikative Inverse? 2006-12-03 16:56
georg
kann man nicht sagen, man sucht die zahl, die mit 2 multipliziert 18 ergibt, weil dann der rest zu 17 gleich 1 ist. also 2 * 8 = 1 in Z_17 ?

In dem Fall ja. Im allgemeinen suchst du aber zu Zahlen m,k
(in dem Fall m=2 und k=17) eine Zahl i so, dass es eine Zahl n
gibt mit m*i=n*k+1. Wenn du nun schon ein n gefunden hast,
von dem du weißt, dass es dazu ein i gibt, kannst du natürlich
das nehmen (in diesem Fall weißt du halt, dass es mit n=1 geht,
wenn also rechts 18 steht).

Das Problem ist nur, dass du im allgemeinen so ein n nicht
kennst. Bei der Suche nach dem Inversen von 4 klappt das mit
18 zum Beispiel nicht, weil 4 kein Teiler von 18 ist.

Hier kommst du nur weiter, wenn du eine Zahl suchst, die mit 4
multipliziert 52 ist (das Inverse von 4 ist 13).

Re: Multiplikative Inverse? 2006-12-03 17:09
Anonymer User
ok danke, das hat mir weitergeholfen, ich werde dann mal versuchen die anderen aufgaben zu lösen.