Задача: для большого десятичного числа $N$ установить, делится ли $N$ на $9$, $11$ и $7$. Приведите самые быстрые практические критерии и ограничьте их применимость.
Критерий для $9$ - Утверждение: $N$ делится на $9$ тогда и только тогда, когда сумма его цифр делится на $9$.
- Обоснование: $10\equiv 1(\mathrm{mod}9)$, поэтому для записи $N=\sum d_{i}10^i$ имеем $N\equiv \sum d_i(\mathrm{mod}9)$.
- Практический способ: вычислить $S=\sum d_i$ (или итеративно сводить сумму цифр), проверить $S\equiv 0(\mathrm{mod}9)$.
- Ограничения: требует чтения всех цифр ($O(n)$ по числу цифр); удобен для человека (простая суммa), даёт ровно остаток по $9$ (а также по $3$). Не сокращает асимптотику — нужен полный просмотр числа.
Критерий для $11$ - Утверждение: $N$ делится на $11$ тогда и только тогда, когда чередующаяся сумма цифр делится на $11$: $N\equiv \sum (-1{)}^i{d}_i(\mathrm{mod}11)$.
- Обоснование: $10\equiv -1(\mathrm{mod}11)$, значит $10^i\equiv (-1{)}^i$.
- Практический способ: вычислить $A={\sum }_i(-1{)}^i{d}_i$ (или поразрядно: прибавлять и вычитать поочерёдно), проверить $A\equiv 0(\mathrm{mod}11)$.
- Ограничения: также $O(n)$; 조금 сложнее для человека (нужна чередующаяся сумма), но даёт остаток по $11$. Для длинных чисел удобно реализовать как $r=(10r+d)\mathrm{mod}11$.
Критерии для $7$ - Общая заметка: для $7$ нет столь тривиальной «суммы цифр», но есть несколько практичных приёмов.
1. Правило «удалить последнюю цифру, вычесть удвоенную последнюю цифру»: для $N=10a+b$ (где $b$ — последняя цифра) число $N$ делится на $7$ тогда и только тогда, когда $a-2b$ делится на $7$.
- Короткое обоснование: $10a+b\equiv 3a+b(\mathrm{mod}7)$ и $3(a-2b)=3a-6b\equiv 3a+b(\mathrm{mod}7)$; так как $3$ обратим по модулю $7$, получаем эквивалентность делимости.
- Практика: повторять операцию, пока не получится небольшое число.
- Ограничения: операция даёт меньший по величине результат не всегда очень быстро, возможны промежуточные отрицательные числа (но с ними удобно работать), для руки надо повторять несколько раз — не самая компактная для человека при очень длинных числах.
2. Правило блоками по $3$ цифры (быстро для больших десятичных записей): поскольку $10^3=1000\equiv -1(\mathrm{mod}7)$, представим $N=\sum B_{i}10^{3i}$ (каждый $B_i$ — блок от $0$ до $999$). Тогда
$$N\equiv \sum (-1{)}^i{B}_i(\mathrm{mod}7).$$ - Практика: складывать/вычитать подряд блоки по $3$ цифры; результат проверить на делимость на $7$.
- Ограничения: уменьшает число операций примерно в $3$ раза по сравнению с покомпонентной обработкой цифр, но приходится работать с трёхзначными блоками.
3. Универсальный (и для компьютера оптимальный) метод: остаток по модулю $m$ вычисляют поразрядно
$$r:=0;\text{для каждой цифры}d:r\leftarrow (10r+d)\mathrm{mod}m.$$ Для $m=7$ это даёт за одну проходку корректный остаток.
- Ограничения: сложность $O(n)$; это оптимально по времени (нельзя решить, не прочитав число).
Сравнение по быстроте и применимости
- Для человека: самый быстрый — критерий для $9$ (сумма цифр), затем $11$ (чередующаяся сумма), для $7$ удобнее блоки по $3$ цифры или правило «удвоить последнюю и вычесть».
- Для машины: универсальный поразрядный модульный алгоритм $r=(10r+d)\mathrm{mod}m$ оптимален и одинаково прост для $m\in \{7,9,11\}$.
- Общий ограничитель: ни один критерий не позволяет избежать чтения всех цифр числа — любой корректный тест требует времени не меньше $O(n)$ по числу цифр (информация о числе должна быть прочитана).
(Кратко: для $9$ — сумма цифр; для $11$ — чередующаяся сумма; для $7$ — правило «a-2b» или блоки по $3$ цифры; для всех трёх оптимально по компьютеру — поразрядное вычисление остатка $r=(10r+d)\mathrm{mod}m$.)