Число кратное N с нечетной суммой цифр

[rightways]

Докажите, что при любом натуральном $N$ можно найти число с нечётной суммой цифр, кратное $N$.

[mathematician123]

Из верности утверждения задачи для $N$ следует верность утверждения для $10^m \cdot N$. Если $N$ начинается с цифры, меньшей чем 5, то верность утверждения задачи для $N$ следует из его верности для $uN$, где $u$ подобрано так, что $uN$ оканчивается на цифру, которая больше 4. Поэтому далее будем считать, что $N$ начинается с цифры, которая больше 4 и заканчивается ненулевой цифрой.

Заметим, что $s(a + b) \equiv s(a) + s(b) + f(a, b) \pmod{2}$, где $s(x)$ и $f(x, y)$ обозначают соответственно сумму цифр числа $x$ и количество переносов, возникающих при сложении в столбик чисел $x$ и $y$.

Подберём число $u$ так, что $uN$ заканчивается на цифру, которая больше 4, а предпоследняя цифра отлична от 9. Если $N$ или $uN$ имеет нечётную сумму цифр, то всё доказано. В противном случае подберём число $k$ так, что при сложении в столбик чисел $10^k \cdot uN$ и $N$ последняя цифра из $uN$ оказалась прямо под первой цифрой числа $N$ (то есть, $k$ равно количеству цифр числа $N$, уменьшенному на 1). Тогда при сложении возникнет ровно один перенос разряда и число $(10^k \cdot u + 1) N$ будет иметь нечётную сумму цифр.

[Shadow]

Будем считать $N$ - взаимнопростое с $10$ - иначе добавлением нужное число нулей в конце. А значин нечетное. Тогда

$1+10^{\varphi(N)}+10^{2\varphi(N)}+\cdots 10^{(N-1)\varphi(N)} \equiv N \equiv 0 \pmod N$

Нечетное число единиц.

[rightways]

Вот, другое решение этой задачи

topic152133.html