Кратные числа с заданной суммой цифр

  Если n кратно 3, то всякое кратное n число кратно и 3. Значит, сумма цифр этого числа кратна 3, поэтому не может быть равной, например,  n + 1.

  Далее считаем, что n не кратно 3. Тогда найдётся решение сравнения  9x ≡ – k (mod n)  в интервале  0 < x ≤ n ≤ k.

  Если n взаимно просто с 10, то  10^a ≡ 1 (mod n)  при некотором натуральном a. Тогда подойдёт число

10(10^a + 10^2a + ... + 10^xa) + (10^a + 10^2a + ... + 10^(k–x)a)  (при  k = x  вторая скобка отсутствует). Его сумма цифр равна  x + (k – x) = k,  а по модулю n оно сравнимо с  10x + (k – x) ≡ 0.

  Если же  n = 2^b5^cd,  где d взаимно просто с 10, то  k ≥ d.  Как показано выше, существует кратное d число с суммой цифр k. Домножив его на 10^max(b,c), получим искомое число.