Найдите остаток от деления числа a ** m, если:

Question

Дан 1 ответ

Правильный ответ

Преобразуем число а:
$a=7\cdot2^{161}+5\cdot18^{75}=7\cdot2\cdot 2^{160}+5\cdot18^{75}= \\\ =14\cdot (2^4)^{40}+5\cdot18^{75}=14\cdot 16^{40}+5\cdot18^{75}= \\\ =14\cdot (17-1)^{40}+5\cdot(17+1)^{75}$

При раскрытии скобок получим следующее (k - некие коэффициенты, рассчитываемые по формуле бинома Ньютона):
$14\cdot (17-1)^{40}+5\cdot(17+1)^{75}= \\\ =14\cdot(17^{40}-k_1\cdot17^{39}\cdot1^1+k_2\cdot17^{38}\cdot1^2-...- k_3\cdot17^{1}\cdot1^{39}+1^{40})+ \\\ +5\cdot(17^{75}+k_4\cdot 17^{74}\cdot 1^1+...+k_5\cdot 17^1\cdot1^{74}+1^{75})$

Заметим, что все слагаемые содержат множитель 17 за исключением двух: последнее слагаемое в первой скобке и последнее слагаемое во второй скобке.

Слагаемые, содержащие множитель 17, дадут при делении на 17 остаток 0, слагаемые, не содержащие множитель 17, выпишем отдельно:
$14\cdot1^{40}+5\cdot1^{75}=14+5=19=17\cdot1+2$
Остаток при делении на 17 этой суммы равен 2, значит и остаток от деления исходного числа на 17 равен 2.

Ответ: 2

Artem112_zn (271k баллов) 02 Май, 18