Wie berechne ich 24 hoch 9 mod 29 ?

[nobody]

Hallo zusammen,

Ich kann ich denn 24 hoch 9 mod 29 berechnen?
Da müßte 25 rauskommen, nur wie komme ich mit einem
normalen taschenrechner darauf? Kann ich die 24 hoch 9
irgendwie auseinanderziehen ?


MfG
Sandro

[Lim_Dul]

24^9 mod 29 = ((24^8 mod 29) * (24^1 mod 29)) mod 29

= ((24^4 mod 29)^2 mod 29) * (24^1 mod 29)) mod 29
usw.

Anders ausgedrückt: (a*b) mod c <=> ((a mod c) * (b mod c)) mod c