Найти остаток от деления числа a=3×2^73+9×16^29 на 17

Решение.

2^8 = 256 = 255 + 1 = 17 x 15 + 1

Т.е. 2^8 дает остаток 1 при делении на 17. Тогда 2^8 в любой степени будет давать остаток 1 при делении на 17 (при умножении чисел остатки умножаются).

2^73 = 2 х 2^72 = 2 х (2^8)^9. Остаток: 2 х 1 = 2

3 × 2^73. Остаток: 3 х 2 = 6

16^29 = (2^4)^29 = 2^116 = 2^4 x 2^112 = 16 x (2^8)^14. Остаток: 16 х 1 = 16

9 × 16^29. Остаток 9 х 16 = 144 = 136 + 8 = 17 х 8 + 8. Остаток 8.

Число а: остаток 6 + 8 = 14.

Ответ: 14.