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