modulo wysokich potęg k: modulo wysokich potęg Witam! Ktoś ogarnia jak takie coś rozwiązać? 77¹³³mod80

Krzysiek: skorzystaj z tego: http://pl.wikipedia.org/wiki/Twierdzenie_Eulera_(teoria_liczb)

Trivial: Bardzo prosto poprzez podnoszenie do kwadratów. Przekształcamy 133 na system binarny: 133 = 128 + 4 + 1 = 2⁷ + 2² + 1 Podnosimy 77 do kwadratu 7 razy (modulo 80): 0 77 1 77² ≡ 9 2 9² ≡ 1 3 1² ≡ 1 4 1 5 1 6 1 7 1 Zatem: 77¹³³ ≡ 77²⁷*77²²*77²⁰ ≡ 1*1*77 ≡ 77 (mod 80)

k: algorytm może i prosty, ale gorzej z liczeniem dzięki!