Frage von Spoon123, 50

Multiplikatives Inverses berechnen?

Moin moin :) Also ich muss in einer Aufgabe alle x Element von Z bestimmen die folgende Kongruenzen erfüllen:

16x = 8 (mod 51) x = 5 (mod 7)

Ist soweit auch nicht so schwer, allerdings gelange ich an einem Punkt an dem ich die Kongruenz

5 = 2b (mod 7)

lösen muss. Dafür benötige ich das multiplikativ Inverse von 2 bzgl. 7. Das multiplikativ Inverse war zuvor ziemlich einfach zu errechnen, allerdings komm ich an der Stelle nicht weiter.

Der ggt(7,2) ist 1

7 = 32 + 1 2 = 21 + 0

Das für das Inverse muss ich ja nun nach 1 umstellen, also:

1 = 7 - 3*2

Bei den vorherigen Inverse hatte ich einen Schritt mehr beim ggT, sodass ich noch weiter einsetzen konnte. Bspw das mult. Inv. von 7 bzgl. 51: ggT (51, 7):

51 = 77 +2 7 = 32 + 1 2 = 2*1 + 0

Nach 1 umgestellt:

1 = 7 - 3*2

Und nun kann ich die oberste Zeile nach 2 umstellen und einsetzen um auf das multiplikativ Inverse zu kommen. Der Schritt fehlt mir allerdings beim mult. Inv von 2 bzgl. 7. Jeder Online-Rechner für eben dieses Inverse spuckt mir als Lösung 4 aus. Allerdings wüsste ich gerne warum und wie man es in dem Fall selbst löst :/

Danke im Vorraus :)

Antwort
von soulflow, 38

Ich weis nicht welches Vorwissen du hast, aber das Lemma von Bezout sagt dir dass du den ggT von 2 und 7 als linearkombination der beiden schreiben kannst und eine Folgerung daraus ist, dass die "Koordinate" vor der 2 dein Multiplikativ inverses zu 2 in Z/(7) ist. Nun hast du ja schon richtig ggT(2,7)=1=7-3*2.
also ist -3 dein multiplikativ Inverses. Nun möchte man natürlich lieber mit positiven Zahlen rechnen. Nun ist aber JEDE Zahl die sich schreiben lässt als -3+m*7 für m aus Z kongruent zu -3. Also auch -3+1*7 =4. Daher ist "auch" 4 das multiplikativ Inverse zu 2.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten