Modulo und Potenzieren

[icarus2]

Ich habe gerade versucht $R_{35}(1761^{4784})$ von Hand zu berechnen und bekomme es nicht hin. Kann mir mal jemand etwas auf die Spruenge helfen?

[Bashar]

icarus2 schrieb:

$R_{35}(1761^{4784})$

Was heißt das? 1761^{4784}\pmod{35}?

[icarus2]

Bashar schrieb:

icarus2 schrieb:

$R_{35}(1761^{4784})$

Was heißt das? 1761^{4784}\pmod{35}?

Ja.

[SeppJ]

Was meinst du denn genau mit "von Hand"? Gehe ich Recht in der Annahme, du hast dies versucht:
http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Further_applications
?

Woran scheiterst du denn?

[Bashar]

Unter Verwendung von
ab\bmod c = (a\bmod c)(b\bmod c) \bmod c
musst du dich langsam voran hangeln.

Hier sähe das so aus:

Von vornherein schonmal 1761 mod 35 berechnen: 1761 = 50*35 + 11 = 11 (mod 35)

Du musst also nur noch 11^4784 berechnen. 4784 ist durch 2 teilbar, also könnte es sinnvoll sein, 11^2 zu berechnen, das ist 121 = 16 (mod 35). Es ist auch durch 4 teilbar, und 11^4 ist 16^2 = 256 = 11 (mod 35) ... und mit dieser Erkenntnis ist man im Prinzip fertig.

[icarus2]

Ok, dann kommt man wohl nicht darum herum $1761 \; mod \; 35$ zu berechnen. Ist etwas muehsam die ganze Rechnerei ohne Taschenrechner.

Ich werds mal versuchen. Danke.