Лемма. Пусть — натуральные числа, Тогда существует число, делящееся на десятичная запись которого представляет многократно повторенную запись числа

Доказательство. Среди чисел есть два числа, дающих одинаковый остаток при делении на (если взять достаточно много чисел больших, чем ). Возьмем их разность и отбросим нули на конце.

_________________________________________________________________________________________________________________________________________________________________________________

Тогда по лемме возьмём в качестве просто произведение всех -значных чисел, составленных из Это число будет, очевидно, взаимно просто с и Теперь в качестве числа для выполнения условия задачи можно взять число, которое содержит сначала очень много единиц, потом очень много троек, семёрок и девяток. Снова получаем по лемме, что каждый блок по отдельности делится на (либо же можно сослаться на то, что приписывание нулей после блока цифр на делимость не влияет). Тогда и всё число тоже будет делится.