Обратные остатки

Как обычно, мы будем заниматься только нечётными Утверждение задачи можно переформулировать так: если при число не кратно то не кратны и все последующие члены последовательности. Положим Пусть ни одно из чисел не делится на Тогда для каждого такого, что не кратно в частности, для всех существует число такое, что Кроме того, положим

Каждому ненулевому остатку при делении на сопоставим обратный остаток такой, что кратно (легко видеть, что разным соответствуют разные Объединим в одну группу остатки и (очевидно, для остатков и получится та же самая группа). Ясно, что остаток не может совпадать с Есть единственная группа, в которой совпадает с (так как если кратно то на делится или и не более одной группы, в которой совпадает с (так как не более чем для двух число кратно Во всех остальных группах по четыре разных остатка. Таким образом, общее количество групп, на которые мы разбили ненулевые остатки при делении на не превосходит Это значит, что среди чисел есть два, попавших в одну группу.

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

Таким образом, если среди нет то их нет и среди всех дальнейших и, следовательно, никакие не кратны