Алгоритм для 9
Правило: целое число делится на $9$ тогда и только тогда, когда сумма его цифр делится на $9$.
Почему это работает: для основания десять $10\equiv 1(\mathrm{mod}9)$, значит для числа $N$ с цифрами $d_i$ (единицы — $d_0$) имеем
$$N=\sum _{i\ge 0}{d}_{i}10^i\equiv \sum _{i\ge 0}{d}_i(\mathrm{mod}9).$$ Поэтому проверка сводится к вычислению суммы цифр по модулю $9$.
Эффективный алгоритм (стриминг, не требует хранения всего числа):
1. Инициализировать $r:=0$.
2. Для каждой цифры $d$ (с любой стороны): $r:=(r+d)\mathrm{mod}9$.
3. В конце $N$ делится на $9$ тогда и только тогда, когда $r=0$.
Сложность: $O(n)$ по числу цифр, память $O(1)$. Можно ускорять объединением блоков цифр (читая, скажем, по 9 цифр и беря число по модулю $9$), но принцип тот же.
Алгоритм для 11
Правило: $N$ делится на $11$ тогда и только тогда, когда альтернирующая сумма цифр делится на $11$ (т. е. разность сумм цифр на чётных и нечётных позициях равна $0$ по модулю $11$).
Почему это работает: $10\equiv -1(\mathrm{mod}11)$, поэтому
$$N=\sum _{i\ge 0}{d}_{i}10^i\equiv \sum _{i\ge 0}{d}_i(-1{)}^i(\mathrm{mod}11).$$
Эффективный алгоритм:
1. Инициализировать $r:=0$, знак $s:=1$.
2. Для каждой цифры $d$ (идя от младших к старшим или наоборот, просто чередовать знак): $r:=(r+s\cdot d)\mathrm{mod}11$, затем $s:=-s$.
3. В конце $N$ делится на $11$ тогда и только тогда, когда $r\equiv 0$.
Альтернатива (универсальный приём): использовать накопление по основанию:
$$r:=(r\cdot 10+d)\mathrm{mod}11$$ для последовательного чтения цифр слева направо; в конце проверить $r=0$. Это тоже работает и обычно наиболее просто реализуется.
Обобщение для других оснований и модулей
Общий факт: для основания счисления $b$ и модуля $m$ положим $r\equiv b\mathrm{mod}m$. Тогда для числа
$$N=\sum _{i\ge 0}{d}_i{b}^i$$ имеем
$$N\equiv \sum _{i\ge 0}{d}_i{r}^i(\mathrm{mod}m).$$ Следствия:
- Если $r\equiv 1(\mathrm{mod}m)$ (т. е. $m\mid (b-1)$), то тест сводится к сумме цифр по модулю $m$ (аналог правила для $3$ и $9$ при $b=10$).
- Если $r\equiv -1(\mathrm{mod}m)$ (т. е. $m\mid (b+1)$), то тест сводится к альтернирующей сумме цифр (аналог для $11$).
- В общем случае порядок элемента $r$ по модулю $m$ равен некоторому $t$; тогда веса $r^i$ периодичны с периодом $t$, и проверка сводится к взвешенной сумме по блокам длины $t$.
Универсальный и эффективный алгоритм для любого $m$: вычислять остаток по модулю $m$ методом Горнера по основанию $b$:
1. $r:=0$.
2. Для каждой цифры $d$ слева направо: $r:=(r\cdot b+d)\mathrm{mod}m$.
3. Число делится на $m$ тогда и только тогда, когда $r=0$.
Сложность этого алгоритма $O(n)$ по числу цифр, память $O(1)$. Он работает для любых $b,m$ (не требуется взаимной простоты), и является практической реализацией всех частных правил, которые получаются при специальных значениях $r$.