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

Answer 2

Для решения этой задачи, мы будем использовать малую теорему Ферма, которая утверждает, что если p - простое число, а a - целое число не делящееся на p, тогда:

a^(p-1) ≡ 1 (mod p)

Также, мы знаем, что если a ≡ b (mod p) и c ≡ d (mod p), тогда:

a + c ≡ b + d (mod p) a * c ≡ b * d (mod p)

Теперь рассмотрим остатки степеней двойки при делении на 55:

2^1 ≡ 2 (mod 55) 2^2 ≡ 4 (mod 55) 2^3 ≡ 8 (mod 55) 2^4 ≡ 16 (mod 55) 2^5 ≡ 32 (mod 55) 2^6 ≡ 9 (mod 55) 2^7 ≡ 18 (mod 55) 2^8 ≡ 7 (mod 55) 2^9 ≡ 14 (mod 55) 2^10 ≡ 28 (mod 55) 2^11 ≡ 1 (mod 55) 2^12 ≡ 2 (mod 55) ...

Заметим, что остатки повторяются каждые 10 степеней двойки. Это происходит, потому что 2^10 = 1024, что даёт остаток 1 при делении на 55, и далее все последующие степени двойки повторяют остатки, которые были в предыдущих 10 степенях.

Теперь давайте рассмотрим степень 27^17. Мы можем представить ее в виде (2^3)^17, так как 27 = 2^3 * 3^3. Подставив вместо 27 значение 2^3 * 3^3, получаем:

(2^3)^17 * 3^51

Теперь можем сократить степени двойки в первом множителе, используя остатки от деления на 10:

(2^3)^17 ≡ 2^7 (mod 55)

Также мы можем сократить степени тройки во втором множителе, используя остатки от деления на 55:

3^51 ≡ 27 (mod 55)

Теперь мы можем объединить два множителя и получить:

2^7 * 27 ≡ 38 (mod 55)

Таким образом, остаток от деления 2^(27^17) на 55 равен 38.