Modulares Potenzieren Erklärung

Question

Aufgabe:

1)     3²⁵⁵ mod 13

2)    4 ^4^4   mod 13

Problem/Ansatz:

ich habe folgende Regeln für Modulares Potenzieren

i) a^b mod m = (a mod m)^b

^{ii) a ^b^c = a ^ b*c}

^{bei der 1)  würde ich vorgehen:}

^{3^5^51 mod 13}

²⁴³ ^ ^{51 mod 13 = 9^51 mod 13     aber weiß ich nicht mehr wie es weiter geht?}

^{1) Lösung = 1}

^{2) Lösung = 9}

Answer 1

\( 3^{255} \bmod 13=\left(3^{3} \bmod 13\right)^{85} \bmod 13=1^{85} \bmod 13=1 \)

Comments

muss das nicht ( (3⁴ mod 13 )⁶³   * 3³ mod 13   ?

denn 63*4+3 = 255

---

ja, kleiner Tippfehler, danke

---

wäre dann die Lösung = -1  ?   weil -1⁶³   = -1

---

Nein, ich hatte mich vertippt und dadurch ein falsches Ergebnis erhalten.

Answer 2

statt 3^255 mod 13 

Vielleicht mal erst 3^8 mod 13 = 81 mod 13 = 3  #

Dann ist 3^256 = 3^(8*8*8)=(3^8)^(8*8) wegen # also

=3^(8*8)=(3^8)^8=3^8=3 mod 13

Und weil 3^255 * 3 =  3^256 , wäre also

3^255 * 3 = 3 mod 13 

also 3^255=1 mod 13

(4^4)^4  mod 13  geht dann so

4^4 = 16*16 = 3*3 = 9  mod 13

(4^4)^4  = 9^4 = 81*81 =  3*3 (siehe # ) = 9 mod 13

Comments

" Vielleicht mal erst 3⁸ mod 13 = 81 mod 13 = 3  "

diese Zeile verstehen ich nicht, denn

3⁸ mod 13 = 81² mod 13 =  3²   mod 13 

also es ist 9 nicht 3 ?!