Multiplikatives Inverse von [75]_256 in Z/256Z

Question

Aufgabe:

Man bestimme das multiplikative Inverse von [75]₂₅₆ in ℤ/256ℤ.

Problem/Ansatz:

Ich kann damit leider nichts anfangen, da die Formulierung irgendwie anders ist als andere Aufgaben, die ich darüber gesehen habe.

Comments

Welche Aufgaben mit ähnlichen Formulierungen kannst Du denn lösen? Wo genau ist das Problem?

---

[75]₂₅₆ hab ich so bei keinen anderen Aufgaben zum Multiplikativen Inverse gesehen und bin mir nicht sicher ob es wirklich einfach nur

75*x ≡ 1 (mod 256)

bedeutet

Andere aufgaben waren immer bspw. 11 in ℤ₁₉

---

Ja, es ist einfach nur 75*x=1 (mod 256)

Übrigens: Bevor Du rechnest, würde ich mal checken, ob es eventuell 257 ist.

---

Okay vielen Dank.

Ja 256 ist richtig, dann müsste doch 99 rauskommen oder?

---

ja, das stimmt - wenn ich mich nicht verfingert habe

Answer 1

ggt(75,256)=1, Du kannst dann mit dem erweiterten Euklidischen Algorithmus rechnen. Damit kommst Du am Ende auf 1=-29*256+99*75, also ist die gesuchte Inverse 99.

Die Probe ist viel leichter als diese Rechnung, kannst Du also leicht selbst prüfen.

Answer 2

Hier noch ein anderer Weg:

\(75 = 3\cdot 5^2\)

Nun ist "zufälligerweise" (?) 255 durch 3 und 5 teilbar. Man erhält:

\(255 \equiv 3\cdot 85 \equiv -1 \mod 256 \Rightarrow -85 \equiv 3^{-1}\mod 256\)

\(255 \equiv 5\cdot 51 \equiv -1 \mod 256 \Rightarrow -51 \equiv 5^{-1}\mod 256\)

Jetzt nur noch multiplizieren (und etwas rechnen):

\(75^{-1} \equiv 51^2\cdot (-85) \equiv 99 \mod 256\)