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

Докажем, что никакой член последовательности не может делиться на число если — отсюда, очевидно, вытекает утверждение задачи.

Рассмотрим числа …, и разберём сначала случай, когда среди них есть число кратное Тогда, очевидно,

и все последующие члены последовательности дают при делении на остаток

Если же среди первых членов последовательности нет кратных то среди них найдутся два сравнимых по модулю Но это означает, что последовательность остатков при делении на периодична, и остаток не встречается ни в периоде, ни в предпериоде.