Задача
NT-B1-M12-P018 Вариант 4. Кратное из нулей и единиц
#18
★★★☆☆ Уровень 3 из 5
Пусть \(\gcd(m,10)=1\). Докажите, что существует число, состоящее только из цифр \(0\) и \(1\), которое делится на \(m\).
Достаточно построить число из одних единиц.
По принципу Дирихле среди \(R_1,\ldots,R_m\) либо одно число делится на \(m\), либо два имеют одинаковый остаток. Во втором случае их разность равна \(10^iR_j\) для некоторого \(j\) и делится на \(m\). Так как \(10^i\) обратимо по модулю \(m\), получаем \(m\mid R_j\). Число \(R_j\) состоит только из единиц, значит также только из цифр \(0\) и \(1\).
Конструктивная задача без явного числа.