7^100 mod 13
Wie kann man dies per Hand ausrechnen?
Mein bisheriger Ansatz ist:
7^100 mod 13
= ((7^2)^2)^25 mod 13
= ((49 mod 13)^2)^25 mod 13
= (10^2)^25 mod 13
= (100 mod 13)^25 mod 13
= 9^25 mod 13
= (9^5)^5 mod 13
= (9 * 9 * 9 * 9 * 9)^5 mod 13
= (81 * 81 * 9)^5 mod 13
= (81 mod 13 * 81 mod 13* 9)^5 mod 13
= (3 * 3 * 9)^5 mod 13
= 81^5 mod 13
= (81 mod 13)^5 mod 13
= 3^5 mod 13
= 3 * 3 * 3 * 3 * 3 mod 13
= 81 * 3 mod 13
= (81 mod 13) * 3 mod 13
= 3 * 3 mod 13
= 9 mod 13
= 9 => r = 9
Doch jeder Rechner sagt mir es kommt 3 raus, also ist da wohl irgendetwas falsch. :D
!
