24^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⁴)¹⁰⁰⁰ wäre, würde ich es hinbekommen, aber 2^{4^1000} verwirrt mich weil ich nicht aus dem Stehgreif weiß, was 4¹⁰⁰⁰ 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¹⁰⁰⁰ mod phi(81) = 4¹⁰⁰⁰ mod 54

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

4¹⁰ mod 54 = 1048576 mod 54 = 4

2⁴ mod 81 = 16 mod 81 = 16

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

4¹⁰ mod 54 = 16⁵ mod 54 = 16 * 16⁴ mod 54 = 16 * 256² mod 54 = 16 * 40² 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 :)