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

Одно из чисел и нечётно; примем, не умаляя общности, что это число Тогда все нечётны, таким образом, это числа в каком-то порядке. Среди чисел находится число поэтому кратно Это невозможно, если у есть нечётный делитель, больший так как в этом случае он находился бы среди и на него бы не делилось. Таким образом, — степень двойки с целым неотрицательным показателем,

При условие задачи, очевидно, удовлетворяется: кратно при число на не делится. Докажем индукцией по что при выражение кратно то есть что на делится При число кратно Пусть Тогда получаем, что

даёт при делении на такой же остаток Осталось заметить, что даёт остаток при делении на