Есть задача, которая гласит: “Наибольшее целое число n, которая разделяет 17^(9)-9^(9)”
Ответы:
А) 3
B) 4
C) 6
D) 7
Ответ А, но в интернете не дается описывающий алгоритм по которому можно самому решить действие. Ничего кроме разложения на многочлены чрез ФСУ и дальнейшие арифметические фокусы с отниманием, прибавлением пока не придумал.
2 лайка
Знаком с малой теоремой Ферма? Попробуй по ней посмотреть какие остатки 17^9-9^9 дает по модулю чисел из вариантов ответа
Погоди,ответ А физически быть не может.17 даёт остаток 2 при делении на 3,а 9 даёт остаток 0 при делении на 3
Чтобы число делилось на n,нужно,чтобы оба числа делились на n,либо остаток у обоих чисел должен быть одинаковый
Подсказка:
если хочешь найти остаток при делении на какое-то n,то ты можешь возвести в степень остаток числа k при делении на n.Например,7^10 сравним(то есть даёт одинаковый остаток) с 2^10 при делении на 5.
Ответом будет 4,то есть B,поскольку 17 и 9 дают остаток 1 при делении на 4.Даже если ты и возводишь 17 и 9 в 9 степень,то все равно остаток 1 и останется(это можно доказать через бином Ньютона).
Доказательство через раскрывание скобки(упрощенный вариант Бинома Ньютона):
(17)^9=(16+1)^9=(16^9+…+1^9)
В последнем выражении каждый член суммы будет делиться на 4,кроме последнего,то есть кроме 1^9,то же самое и с 9^9.После ты вычитаешь первое от второго,убирая первый 1^9 от второго.В итоге,останутся только числа,которые делятся на 4
Модуль 4 можно просто как 17^9 -9^9 \equiv 1^9 - 1^9 \equiv 0 \mod{4}