Задачи наших читателейЗадачи наших читателей // Квант. — 1977. — № 4. — С. 59.‍‍

Разобьём двоичную запись натурального числа $a$‍‍ с конца на группы вида $10^k$‍.‍ Например, $a=1011000100$‍‍ разбивается так: $$ \underbrace{10}_{\textstyle a_4}~ \underbrace{1}_{\textstyle a_3}~ \underbrace{1000}_{\textstyle a_2}~ \underbrace{100}_{\textstyle a_1}. $$

Через $a'$‍‍ обозначим число, полученное из данного вычёркиванием его последней группы $a_1$‍,‍ а через $a\otimes b$‍‍ обозначим число, образованное приписыванием к $a$‍‍ справа числа $b$‍‍ (в этих обозначениях $a=a_n\otimes a_{n-1}\otimes\ldots\otimes a_2\otimes a_1$‍).‍

Докажите, что для любого натурального числа $a$‍‍ и нечётного натурального $b$‍‍ справедливы следующие утверждения:

1. $ab=((\ldots((b'\otimes a_n+b')\otimes a_{n-1}+b')\otimes\ldots)\otimes a_2+b')\otimes a_1$‍‍ (здесь $a_i$‍‍ — группы разбиения $a$‍,‍ $i=1$‍,‍ 2, $\ldots$‍,‍ $n$‍);‍
2. $a$‍‍ делится на $b$‍‍ тогда и только тогда, когда некоторый член последовательности $$ c_1=a,\quad c_2=c_1'-b',\quad c_3=c_2'-b',\quad\ldots,\quad c_{k+1}=c_k'-b', \quad\ldots $$ равен нулю; при этом, если $c_{n+1}=0$‍,‍ то $\dfrac ab=(c_n)_1\otimes (c_{n-1})_1\otimes\ldots\otimes(c_1)_1$‍.‍

В. Абрамович (г. Ростов-на-Дону)