Aufgabe:
Man bestimme das multiplikative Inverse von [75]256 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.
Welche Aufgaben mit ähnlichen Formulierungen kannst Du denn lösen? Wo genau ist das Problem?
[75]256 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 ℤ19
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
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.
Hier noch ein anderer Weg:
75=3⋅5275 = 3\cdot 5^275=3⋅52
Nun ist "zufälligerweise" (?) 255 durch 3 und 5 teilbar. Man erhält:
255≡3⋅85≡−1mod 256⇒−85≡3−1mod 256255 \equiv 3\cdot 85 \equiv -1 \mod 256 \Rightarrow -85 \equiv 3^{-1}\mod 256255≡3⋅85≡−1mod256⇒−85≡3−1mod256
255≡5⋅51≡−1mod 256⇒−51≡5−1mod 256255 \equiv 5\cdot 51 \equiv -1 \mod 256 \Rightarrow -51 \equiv 5^{-1}\mod 256255≡5⋅51≡−1mod256⇒−51≡5−1mod256
Jetzt nur noch multiplizieren (und etwas rechnen):
75−1≡512⋅(−85)≡99mod 25675^{-1} \equiv 51^2\cdot (-85) \equiv 99 \mod 25675−1≡512⋅(−85)≡99mod256
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos
