Найти остаток от числа:

(7*2^161+5*18^75) : 17

Задача на формулу бинома и делимость.

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