0 Daumen
458 Aufrufe

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. :)

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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.

Avatar von 477 k 🚀

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community