Периодичность и зацикливание

Предположим противное – пусть существует такое, что ни один не делится на Рассмотрим последовательность составленную из остатков по модулю Тогда, разумеется, Поскольку последовательность бесконечная, а множество различных троек остатков по модулю конечно, обязательно найдутся такие натуральные и , что Так как каждое число в последовательности однозначно задается своими тремя предшественниками, то для любого справедливо, что а значит последовательность является периодической с периодом и, возможно, с некоторым предпериодом.

Предположим, что последовательность содержит предпериод. Обозначим его длину как Итак, для любого справедливо, что но (в противном случае не является частью предпериода). Рассмотрим следующую цепочку сравнения по модулю

Первое равенство выполнено по определению последовательности второе – поскольку и входят в периодическую часть последовательности; третье – поскольку четвертое – снова по определению последовательности

Посмотрим на третье и пятое выражение. Из них следует, что что противоречит нашему предположению. Значит, у последовательности предпериод отсутствует, и тогда С другой стороны, Левая часть и первое слагаемое правой части сравнимы с 1 по модулю значит второе слагаемое правой части, делится на Отсюда делится на а существование именно такого элемента нужно было найти по условию.