Question

Найти остаток от числа: (7*2^161+5*18^75):17

Answer 1

Задача на формулу бинома и делимость.
18=(17+1)

(a+b)ⁿ=aⁿ+naⁿ⁻¹b+(n(n-1)/2)aⁿ⁻²+... +nabⁿ⁻¹+bⁿ
Все слагаемые кроме последнего содержат множитель а в степени или просто а, значит кратны а.

18⁷⁵=(17+1)⁷⁵=17⁷⁵+ ... +1⁷⁵
5·18⁷⁵=5·(17⁷⁵+ ... +1⁷⁵)
5·18⁷⁵:17 = частное ( и остаток 5)

аналогично
2¹⁶¹=2·2¹⁶⁰=2·(2⁵)³²=2·(32)³²
32=34-2
(32)³²=(34-2)³²
последнее слагаемое не содержит множителя 34.
Значит
7·2¹⁶¹=7·2·(34-2)³²=14·2³²·(17³²-...+1³²)

Значит остаток от деления 7·2¹⁶¹ на 17 равен остатку от деления 14·2³² на 17.

2³²=2²·2³⁰=4·(2⁵)⁶=4·32⁶=4·(34-2)⁶=4·2⁶·(17-1)⁶=2⁸·(17-1)⁶

14·2³² =14·2⁸·(17-1)⁶
остаток от деления 14·2³²  на 17 равен остатку от деления
14·2⁸=14·256=14·(17·15+1)=(14·17·15+14) на 17 а этот остаток равен 14
Сумма остатков
14+5=19=17+2
Остаток от деления данного числа на 17 равен 2