Быстрая задача на вычисление остатка от деления 13! на 17. Конечно, понятно, что остаток не может быть равен 0, ведь 17 — простое число и не представимо никаким образом как произведение множителей от 1 до 13.
Простейший пример модулярной арифметики в жизни. Числа на циферблате сравнимы по модулю 12. Например 1 mod 12 = 13 mod 12 = 1, 3 mod 12 = 15 mod 12 = 3 и т.д.
Да, в компьютерный век вычислить "какой-то" 13! проще простого. Однако, я хочу рассказать Вам про метод, который позволит Вам делать вычисление остатков на бумаге. Поехали:
Операция "mod" — выдает остаток от деления числа на другое. Примечательно, что результат выполнения этой операции может быть и отрицательным (я буду часто использовать это). Итак, используем определение модулярной арифметики:
Теперь начинаем приводить множители в удобный для вычисления вид и получаем результат:
Просто постарайтесь не запутаться в вычислениях. Например, в третьей строчке я специально умножил 8,2 и 2, чтобы получить 32, которое по модулю 17 равно 15 и т.д. Как приводить множители — дело вкуса. В итоге получаем, что остаток от деления равен 3. Можете проверить на калькуляторе. Спасибо за внимание!
