Działania modulo 124^28MOD11, 324^157MOD7

Question

Witajcie, mam problem z następującymi działaniami modulo:
a) 124^28MOD11
b) 324^157MOD7

a) rozpisałem w następujący sposób:
124^28MOD11=(11*11+3)^28MOD11=3^28MOD11=...

i tu nie wiem jak uzyskać potęgę 28, zacząłem robić to tak:

3^2MOD11=9
(3^2)^2MOD11=9^2MOD11=4
(3^4)^2MOD11=4^2MOD11=3
(3^8)^2MOD11=3^2MOD11=9

a tu zacząłem się zastanawiać, czy rozpisać następną potęgę jako 3^32 i następnie zrobić 3^-4 i to od siebie odjąć, czy może (co wydaje mi się bardziej sensownie) wziąć (3^16)^1,75MOD11=9^1,75MOD11 ale wtedy wychodzi dość nie ładna liczba n. Wynik zadania a) powinien wynieść 5, a zadania b) 2.

Bardzo proszę o pomoc w wykonaniu tych dwóch zadań. Pozdrawiam :)

Answer 1

Doszedłem do rozwiązania.

Ćwiczenie a)

124^28 = 3^28 = ((3^7)^2)^2 = (3^7)^4 = 2187^4 = 9^4 = 6561 = 5 (mod 11)

 

Ćwiczenie b)

324^157 = 2^157 = 2^147 * 2^10 = 2^0 * 2^10 = 1 * 1024 = 1 * 2  = 2 (mod 7)

 

Ps. Dawno nie robiłem zadań z modulo, więc w moich obliczeniach może być ukryty błąd.

Comments

Oki, dzięki za rozwiązanie. Jeśli ktoś sprawdzi i potwierdzi, że dobrze to dam "ptaszka"(?) :D

---

Mógłbyś wytłumaczyć skąd z 2^147 otrzymałeś 2^0?

---

Ponieważ modulo 7 ze 147 to 0

---

Faktycznie, dziękuję!