алгебра - Признаки делимости в двоичной системе счисления

Отвечу на этот вопрос в общем виде.
Пусть $%p$% - основание системы счисления (2, в данном случае), $%k_i$% ($%i\in\mathbb{N}$%) - цифры нашего $%p$%-ичного числа. Тогда пусть $%s_{i,n}$% - сумма цифр в разрядах, номер которых равен $%i$% по модулю $%n$%: $$s_{i,n}=\sum_{k=0}^\infty k_{i+kn}$$ Тогда делимость числа на некоторое число $%m$% равнозначна делимости $%S$% на $%m$%, где: $$S=\sum_{i=1}^n p^i s_{i,n}$$ $$n=\min_i(p^i-1=0 \mod m)$$ Для удобства расчета $%p^i$% в первой формуле можно заменить на любое число, равное ему по модулю $%m$%.
По данным формулам, признаки делимости двоичного числа:

• на 5: $%s_{1,4}-s_{3,4}+2(s_{2,4}-s_{4,4})$% делится на 5
• на 7: $%s_{1,3}+2s_{2,3}-3s_{3,3}$% делится на 7
• на 9: $%s_{1,6}-s_{4,6}+2(s_{2,6}-s_{5,6})+4(s_{3,6}-s_{6,6})$% делится на 9

Проверка делимости на 9 не такая уж быстрая, поэтому лучше сначала проверить делимость на 3