Найти остаток от деления 2^(27^17) на 55. Просьба доходчиво объяснить решение.

Question

Найти остаток от деления 2^(27^17) на 55.
Просьба доходчиво объяснить решение.

Answer 1

(A ≡ B mod C) ⇔ (A*A ≡ A*B mod C)
т.е.
x^y mod z ≡ (((((x mod z) * x) mod z) * x) mod z).....(y раз)...  * x) mod z)
анадогично со степенями
(A ≡ B mod C) ⇔ (A^D ≡ (B mod C)^D mod C)

основываясь на этом
вот код

number = 2
power = 27
ppower = 17
root = 55

# (number**(power**ppower)) % root

rest=number

for i in 1..ppower
    rest = (rest**power) % root
end
return rest

ответ 18

Comments

Его все обязаны знать?

---

никто не обязан, но можно считать что это алгоритм, это и есть просто алгоритм

---

Да, это проще чем объяснять, почему указан код на Ruby...

---

а почему это надо обьяснять? псевдо код да и все

---

Хотя бы потому, что псевдокод, содержащий метод p из Ruby, неочевиден.

---

методов тут нет. что именно не очевидно? я исправлю

---

Да ну? Хотите сказать, что p (как и print, printf, display...) - это в Ruby не методы вывода? Почитайте описание языка.

---

не заметила

---

Спасибо, вчера я решил её и сам, оказалось просто через теорему Эйлера.
Дискретная математика 1 курс.

---

с ответом сошлось