mod (7^31 * 2^1107 * 32^21 , 13)

Question

Ich könnt etwas Hilfe gebrauchen.


Die Aufgabe lautet: Bestimmen Sie mod (7^31 * 2^1107 * 32^21 , 13).

Ich weiß, dass die Lösung 4 ist, aber nicht den Lösungsweg...

Answer 1

Es gilt zumindest

MOD(a^b, 13) = MOD(a, 13)^b
und
a^{2b} = (a^2)^b

Damit mache ich jetzt meine Vereinfachungen:

7^31
--> 7 * 7^30
--> 7 * 49^15
--> 7 * 10^15
--> 70 * 10^14
--> 5 * 100^7
--> 5 * 9^7
--> 45 * 9^6
--> 6 * 81^3
--> 6 * 3^3
--> 18 * 9
--> 5 * 9
--> 45
--> 6

2^1107
--> 2 * 4^553
--> 8 * 4^552
--> 8 * 16^276
--> 8 * 3^276
--> 8 * 9^138
--> 8 * 81^69
--> 8 * 3^69
--> 24 * 3^68
--> 11 * 9^34
--> 11 * 81^17
--> 11 * 3^17
--> 33 * 3^16
--> 7 * 9^8
--> 7 * 81^4
--> 7 * 3^4
--> 7 * 9^2
--> 7 * 81
--> 7 * 3
--> 21
--> 8

32^21
--> 6^21
--> ...
--> 5

Daraus folgt

7^31 * 2^1107 * 32^21
--> 6 * 8 * 5
--> 48 * 5
--> 9 * 5
--> 45
--> 6

MOD(7^31 * 2^1107 * 32^21, 13) = 6

Answer 2

Man kann auch ein wenig zerlegen und passend wieder zusammenfügen:

mod (7^31 * 2^1107 * 32^21 , 13) =

mod (7^31 * 2^31 * 2^{1107-31-21} * 2^21 * 32^21 , 13) =

mod (7^31 * 2^31 * 2^{1107-31-21} * 2^21 * 32^21 , 13) =

mod (14^31 * 2^1055 * 64^21 , 13) =

mod (14^31 * 2^{6*175+5} * 64^21 , 13) =

mod (2^5 , 13) = 6

Verwendet wurde mod(14 , 13) = 1 und mod(64 , 13) = −1.

Das ist wesentlich kürzer, aber vielleicht geht es noch kürzer.