За­ме­тим, что n, крат­ное трем, нам не по­дой­дет, по­сколь­ку при мы по­лу­чим, что число с сум­мой цифр, не крат­ной 3, будет де­лить­ся на 3. По­ка­жем, что все осталь­ные числа нам по­дой­дут.

Рас­смот­рим слу­чай, когда n не крат­но двум, трем и пяти. Так как n вза­им­но про­сто с 9, то най­дет­ся такое, что Тогда

Су­ще­ству­ет такое d, что Дей­стви­тель­но, среди остат­ков чисел 10, 10², 10³, ..., 10ⁿ по мо­ду­лю n долж­ны быть два оди­на­ко­вых (по­сколь­ку всего не­ну­ле­вой оста­ток). Пусть это остат­ки сте­пе­ней 10^a и 10^b тогда так как 10 и n вза­им­но про­сты. (По тео­ре­ме Эй­ле­ра то есть в ка­че­стве d может быть вы­бра­но число всех чисел от 1 до n, вза­им­но про­стых с n.) Зна­чит,

при этом не­слож­но за­ме­тить, что сумма цифр числа N равна k.

Оста­лось рас­смот­реть слу­чай, когда где n₀ не крат­но двум, трем и пяти. В этом слу­чае мы уже умеем стро­ить число N₀ с сум­мой цифр k, крат­ное n₀. Тогда по-преж­не­му будет иметь сумму цифр k, но те­перь уже будет крат­но n.

Ответ: при всех на­ту­раль­ных n, не крат­ных трем.