Modulo mit hohen Potenzen

Aufrufe: 808     Aktiv: 11.02.2020 um 19:01
0

Wie rechne ich 3^12 mod 82? Ich weiß, dass das Ergebnis 81 ist. Nur weiß ich noch nicht genau wie ich drauf komme. Das Square and Multiply Verfahren kenn ich und hab es versucht anzuwenden nur kam ich da ab einen bestimmten Punkt nicht weiter. Kann man mir jemand vielleicht bitte einen "allgemeinen"  Weg zeigen wie man solche Aufgaben mit hohen Potenzen einfach lösen kann?

Viele Dank im Vorraus!

Diese Frage melden
gefragt

Student, Punkte: 10

 
Kommentar schreiben
1 Antwort
1

Hallo,

ich würde es folgendermaßen rechnen. 

Da \( 3^2 = 9 \) und \( 9^2 = 81 \), formen wir um zu

$$ 3^{12} \mod 82 \equiv (3^4)^3 \mod 82 \equiv 81^3 \mod 82 \equiv (-1)^3 \mod 82 \equiv -1 \mod 82 \equiv 81 $$

Grüße Christian

Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 29.81K

 
Nice!! Danke!   ─   samo 11.02.2020 um 18:02
Sehr gerne :)   ─   christian_strack 11.02.2020 um 19:01

Kommentar schreiben