Метод спуска, индукция и последовательное конструирование в ТЧ

Если кратно то все числа, кратные тоже заканчиваются на Значит, они не шаткие. Если кратно то последние две цифры любого числа, кратного могут быть или Значит, они не шаткие. Теперь мы покажем, что только эти числа не являются делителем никакого шаткого числа.

Вначале рассмотрим нечётные числа не кратные Ясно, что НОД также НОД для любого Значит, существует такое положительное что откуда Преобразуем:

Следовательно кратно при любом В частности, — шаткое кратное Если кратно то — шаткое кратное

Теперь рассмотрим степени Докажем индукцией по что имеет шаткое кратное с ненулевыми цифрами. Для можно взять Предположим, что существует для некоторого Значит, Пусть где будет выбрано позже. Ясно, что шаткое и имеет в точности ненулевую цифру. Поскольку кратно тогда и только тогда, когда или мы всегда сможет подобрать значение среди и Доказали. Значит, любая степень имеет шаткое кратное.

Наконец, числа вида где и НОД Такие числа име.т шаткие кратные вида