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

При получаем, что делится на Значит, — это степень двойки. Пусть Тогда делится на Обозначим за число (в двоичной системе счисления это единичек). Покажем, что Для этого докажем, что при

Действительно, и

Значит, можно применить алгоритм Евклида для индексов, что и хотели получить. Тогда из делимости на следует, что делится на для всех целых неотрицательных Заметим, что мы получили даже более сильное утверждение, чем в условии, так что можно аналогично получить и так далее. Тогда все подходящие имеют вид башенки из степеней двоек: Башенки высоты 0, 1, 2, 3 подходят Для башенки высоты 4 можно подставить Тогда не делится на Но по такой логике для любой более высокой башенки мы сможем спуститься до высоты 4 и получить там противоречие. Значит, они тоже не подходят.