Оценка + пример в задачах по теории чисел

Подсказка 1

Вспомним, что сумма цифр неразрывна связана с признаком делимости на 3 и на 9, поэтому что можно сказать про наше число N?

Подсказка 2

Верно, N делится на 9, а значит уже можно перебирать числа все числа кратные 9 и надеяться, что через небольшое время найдётся то самое наименьшее подходящее. Но можно попытаться ещё сократить перебор! Для этого нам нужно найти такой делитель d, который был бы взаимно прост с 9, т.е. не делился бы на 3, чтобы мы могли проверять только числа вида 9dk, где k - натуральное число. А какой признак нам поможет сказать, что число не делится на 3?)

Подсказка 3

Можно снова воспользоваться, тем, что если сумма цифр числа НЕ делится на 3, то и само число НЕ делится на 3. Тогда каким свойством может обладать d?

Подсказка 4

Например, 8 не делится на 3, а значит можно взять d с суммой цифр 8, остаётся только перебрать все числа d с суммой цифр 8 в порядке возрастания.