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 нулей. Ясно, что и в этом случае число построено верно.

Answer 2

Для доказательства этого факта воспользуемся методом математической индукции.

Шаг базы: При s = 1 рассмотрим n = 1, сумма цифр которого равна 1, и 1 действительно делится на 1.

Шаг предположения: Предположим, что для некоторого натурального числа k существует натуральное число m с суммой цифр k, делящееся на k.

Шаг индукции: Докажем, что для k + 1 также найдется соответствующее число. Рассмотрим число m' = 10^p * m, где p выбирается достаточно большим, чтобы сумма цифр m' была больше k + 1. Заметим, что сумма цифр числа m' равна сумме цифр числа m, умноженной на 10^p, плюс некоторая сумма цифр числа m (возможно, равная нулю), которая добавляется в конец числа m' в виде нулей.

Таким образом, сумма цифр m' равна k + 1 + сумме цифр числа m, умноженной на (10^p - 1). Заметим, что (10^p - 1) делится на 9 для любого натурального p. По предположению индукции, существует натуральное число m с суммой цифр k, делящееся на k. Поэтому сумма цифр m' делится на k + 1.

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