schnelles modulares potenzien < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
hallo ihr, ich soll 38^57 mod 103 berechnen..
ich konnte wegen krankheit die Vorlesung nicht besuchen, und weiß nun gar nicht schnellles modulares Potenzieren funktioniert..
Kann mir jeamdn helfen?
Lg sandra
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:05 Mo 27.11.2006 | | Autor: | statler |
Mahlzeit Sandra!
> hallo ihr, ich soll 38^57 mod 103 berechnen..
>
> ich konnte wegen krankheit die Vorlesung nicht besuchen,
> und weiß nun gar nicht schnellles modulares Potenzieren
> funktioniert..
Du kannst bei [mm] \equiv [/mm] mod 103 fast so rechnen wie mit dem Gleichheitszeichen, also:
[mm] 38^{57} \equiv [/mm] 38 [mm] \* (38^{2})^{28} \equiv [/mm] ?
Jetzt kannst du zeigen, ob du in der gewöhnlichen Potenzrechnung fit bist. Du mußt einfach weiter geschickt umformen.
Ich bin übrigens am Ende auf 8 gekommen, aber das ist ohne Gewähr.
Gruß aus HH-Hamburg
Dieter
|
|
|
| |
|
Ich verstehe aber nicht, wie ich das mit den modulo 103 hier einbringe...
Ich kann natürlich weiter umformen, aber dann??
Hatte mich übrigens vertippt ..es war 38^75
kann mir jemand evtl weiterhelfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:31 Di 28.11.2006 | | Autor: | statler |
Mahlzeit Sandra!
Es ist
[mm] 38^{75} [/mm] = 38 [mm] \* (38^{2})^{37} \equiv [/mm] ...
Nebenrechnung:
38 [mm] \* [/mm] 38 = 1444 = 14 [mm] \* [/mm] 103 + 2 [mm] \equiv [/mm] 2 mod 103
... [mm] \equiv [/mm] 38 [mm] \* 2^{37} [/mm] = 38 [mm] \* (2^{7})^{5} \* 2^{2} \equiv [/mm] ...
NR:
[mm] 2^{7} [/mm] = 128 = 103 + 25 [mm] \equiv [/mm] 25
... [mm] \equiv [/mm] 38 [mm] \* 25^{5} \* [/mm] 4 [mm] \equiv [/mm] ...
NR:
[mm] 25^{2} [/mm] = 625 = 6 [mm] \* [/mm] 103 + 7 [mm] \equiv [/mm] 7 mod 103, also
[mm] 25^{4} \equiv [/mm] 49
... [mm] \equiv [/mm] 38 [mm] \* [/mm] 49 [mm] \* [/mm] 25 [mm] \* [/mm] 4 [mm] \equiv [/mm] ...
NR:
4 [mm] \* [/mm] 25 = 103 + (-3) [mm] \equiv [/mm] -3
... [mm] \equiv [/mm] 38 [mm] \* [/mm] 49 [mm] \* [/mm] (-3) = ((-3) [mm] \* [/mm] 38) [mm] \* [/mm] 49 [mm] \equiv [/mm] -11 [mm] \* [/mm] 49 = -539 [mm] \equiv [/mm] -24 [mm] \equiv [/mm] 79
Bitte nachrechnen und liebe Grüße
Dieter
|
|
|
|
