Решение задачи 414

Условие:

Докажите, что среди чисел, записываемых только цифрами 1 и 0, найдется число, кратное 414414.

Решение:

Рассмотрим все числа, состоящие только из единиц: 1, 11, 111, 1111, и т.д.

Рассмотрим все остатки, которые дают эти числа при делении на 414414. Выпишем их в ряд по порядку. Заметим, что теоретически возможны 414414 различных остатка (некоторое конечное число). Поскольку ряд из остатков бесконечен, то рано или поздно найдутся повторяющиеся остатки (или просто найдется число, которое будет давать остаток 0, оно и будет делиться на 414414). Тогда разность двух чисел, дающих одинаковые остатки, будет делиться на 414414. Это число будет иметь вид 111...111000...000 (если из большего вычесть меньшее).