Question

Доказать, что для каждого натурального числа s существует натуральное число n с суммой цифр s, делящееся на s.

Answer 1

Рассмотрим последовательность k-эй член которой определяется так:

$a_k\equiv 10^k \mod s$

причем это число неотрицательно, и меньше s. Проще говоря, это остаток от деления 10^n на s. Ясно, что последовательность периодична и ее период не больше s. Обозначим ее период t.

Теперь рассмотрим число записанное последовательностью цифр $b_0, b_1, b_2, ...$. То есть число

$B=b_0+10b_1+10^2b_2+...$

Очевидно, что

$B\equiv a_0b_0 + a_1b_1 + a_2b_2 + ... \mod s$

Возьмем такое число $n$, что $b_{mt}=1$, для $m=0,1,2,...,s-1$ и $b_k=0$ во всех остальных случаях. Иными словами возьмем число которое стоит из s периодических блоков состоящих из $t-1$ нуля и одной единицы в конце.

Тогда наше число будет состоять из s единиц и какого-то кол-ва нулей. В этом случае, сумма цифра числа s, как и требовалось. Также

$n\equiv sa_0b_0 \equiv 0 \mod s$

Таким образом, оба требуемых условия оказались удовлетворены.

Приведенное выше рассуждение не проходит, если s делится на какую-то степень 10, т. е. оканчивается N нулями. В этом случае построим число n для $s/10^N$, только возьмем блоков $s$, а не $s/10^N$. После этого припишем к результату N нулей. Ясно, что и в этом случае число построено верно.