Modulo Rechnungen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:36 Di 14.02.2006 | | Autor: | DAB268 |
| Aufgabe | Löse die Gleichung [mm] 27^{-1}=x \mod40
[/mm]
Lösung: [mm] 27^{-1}=3 \mod40 [/mm] |
Hallo.
Wie kann ich Gleichungen der Form [mm] $s^{-t}=x\mod [/mm] n$ ; s,t,n gegeben und t>0 mit einem handelsüblichen Schulrechner lösen?
MfG
Christian
|
|
| |
|
Hallo und guten Morgen,
wir betrachten also allgemein das Problem, Inverse in [mm] \IZ\slash n\IZ [/mm] zu berechnen.
Zu solchem n und [mm] a\in\{0,\ldots n-1\} [/mm] gibt es ein Inverses [mm] b=a^{-1} [/mm] - also ein
[mm] b\in\{0,\ldots , n-1\} [/mm] mit ab =1 modulo n - genau dann, wenn ggt(a,n)=1.
Denn es gilt
a invertierbar modulo n [mm] \Leftrightarrow
[/mm]
[mm] \exists\: b\in\{0,1,\ldots , n-1\}\:\: ab\equiv 1\:\mod\: n\:\:\:\Leftrightarrow
[/mm]
[mm] \exists\: s,t\in \IZ\:\: sa+tn\: [/mm] = 1 [mm] \:\:\:\Leftrightarrow
[/mm]
ggt(a,n)=1
Dabei folgt das [mm] ''\Leftarrow'' [/mm] der letzten Äquivalenz zB.
aus dem Erweiterten Euklidischen Algorithmus, und diesen kann man
zur Berechnung von Inversen modulo n verwenden. Wenn gewuenscht, kann
ich diesen Algorithmus noch nachliefern, er ist aber auch gut in der Literatur zu finden.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:44 Mi 15.02.2006 | | Autor: | DAB268 |
Danke! Hab es verstanden!
|
|
|
|
