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


			
Допустим противное, пусть число M и все кратные числу M имеют  четную сумму  
 цифр. Если десятичная запись M оканчивается нулями, все их  
 можно  отбросить,  отбросив столько же нулей и у всех кратных M.  
 Это на сумму цифр не влияет. Итак, пусть M не оканчивается  
 нулями.  
 Рассмотрим сначала случай, когда предпоследняя цифра M - не  
 девятка. Пусть запись числа M содержит n знаков.  
 Можно найти число из n+1 цифры, делящееся на M, десятичная запись  
 которого начинается с данной цифры b.  
 В самом деле, среди 10n последовательных чисел  
 b*10n, b*10n+1, ... , (b+1)*10n-1  
 найдется число, делящееся на M (поскольку M<10n).  
 Итак, можно рассмотреть число S из n+1 цифры, начинающееся  
 на цифру 9 и делящееся на M.  
 Сложим числа S и M*10n.  
 Поскольку число S начинается на 9, а число M не заканчивается на  
 0, при сложении чисел S и M*10n столбиком возникнет  
 перенос в n-ом (считая слева) разряде.  
 Перенос будет ровно в одном разряде, так как предпоследняя цифра M  
 - не девятка. Следовательно, сумма цифр числа S+M*10n  
 на 9 меньше, чем сумма цифр числа S, сложенная с суммой цифр числа  
 M*10n. Таким образом, сумма цифр числа S+M*10n  
 нечетна - противоречие.  
 Рассмотрим теперь случай, когда предпоследняя цифра числа M  
 - девятка. Тогда рассмотрим последовательность 3M, 9M, 27M ...  
 (последовательные умножения на 3).  
 Проследив, как при умножении на 3 меняются последние две цифры,  
 нетрудно понять, что  
 в этой последовательности найдется  
 число, предпоследняя цифра которого - не девятка  
 (при этом последняя цифра этого числа - не ноль). Для этого числа  
 повторяем предыдущие рассуждения.
			
Десятичная система счисления