Berechne ohne Taschenrechner: 74^(11) mod 77

Question

Aufgabe:

Berechne ohne Taschenrechner: 74^(11) mod 77

Problem/Ansatz:

Ich habe es so probiert: 11 kann man auf 9+2 zerlegen z.B.

also : 74^11 mod 77 = ((74^2 mod 77) * (74^9 mod 77)) mod 77 aber jetzt weiß ich nicht wie ich das weiter machen soll, bzw. wie ich zum Ergebnis kommen soll.

Ich wäre sehr dankbar wenn mir jemand helfen könnte. :)

Answer 1

74^2 mod 77
= (-3)^2 mod 77
= 9 mod 77

Ich denke das sollte man eigentlich fast so runterschreiben können.

74^9 mod 77
=  74 * 74^8 mod 77
=  (-3) * (74^2)^4 mod 77
=  (-3) * 9^4 mod 77
=  (-3) * 81^2 mod 77
=  (-3) * 4^2 mod 77
=  (-3) * 16 mod 77
=  -48 mod 77
= 29 mod 77

Und das ist jetzt ohne sich grundlegende gedanken über vereinfachungen zu machen.

Comments

Ach, das macht Sinn! Vielen Dank für die Tolle Antwort.