2^{4^1000} mod 81 =? (bitte um Rechenweg)

Question

Durch wolfram alpha weiß ich, dass das Ergebnis 16 ist. Aber ich brauche Hilfe beim Rechenweg. Wenn es (2^4)^1000 wäre, würde ich es hinbekommen, aber 2^{4^1000} verwirrt mich weil ich nicht aus dem Stehgreif weiß, was 4^1000 ist :D. Und während einer KLausur schon mal gar nicht.

Bitte eine ErlÄuterung oder wenn möglich die ganze Rechnung. (Module Rechnungen bereiten mir keine Probleme :) )

Answer 1

(2)^{4^1000} mod 81

4^1000 mod phi(81) = 4^1000 mod 54

1000 mod phi(54) = 1000 mod 18 = 10

4^10 mod 54 = 1048576 mod 54 = 4

2^4 mod 81 = 16 mod 81 = 16

Achtung. Bei 4^10 braucht man das natürlich nicht ausrechnen. Man kann auch so rechnen

4^10 mod 54 = 16^5 mod 54 = 16 * 16^4 mod 54 = 16 * 256^2 mod 54 = 16 * 40^2 mod 54 = 16 * 1600 mod 54 = 16 * 34 mod 54 = 544 mod 54 = 4

Comments

ah wow noch so spät gelöst. vielen lieben dank :) super dass es mit der phi funktion fkt. hatte das ganz verdrängt :D

---

Ich kenne die Phi-Funktion nicht auswendig. Und die Auswendig lernen ist auch blöd. Dann müsste das eine Klausur mit Hilfsmittel sein. Ist das so?

---

nein wir müssen die Fkt können, aber das kein Prolem. ich wusste einfach nicht, dass man sie so anwenden kann. so macht es natürlich mehr sinn.Nochmal vielen dank :)