Не кажется ли вам, что данная задача слишком сложно решается. Эта задача письменного экзамена (1 час). Причем это задача не в рамках какой-то всероссийской олимпиады по математике школьников или студентов мехматов.
Видите ли, эта задача слишком хорошо известна (возможно, в узких кругах, но тем не менее): см., например, задачу 25 в задачнике Серпинского "250 задач по элементарной теории чисел".
С уточнением: изготовить ещё одну делимость на

Я имел в виду следующее: если

и

, то

, где

(при подходящем выборе

). Можно также (как у Серпинского) рассмотреть

--- порядок двойки по модулю

(и показать, что

).
Не совсем понятно доказательство Шинцеля в задачнике Серпинского:
1) Почему, если

, делается вывод, что

.
2) Почему делается итоговый вывод: число

имеет делитель

и

, а значит, также и простой делитель с этим свойством, что противоречит определению числа

. Правильно ли я понимаю это так:

, в свою очередь число

должно делится на какое-то простое число, допустим

, но

не может быть, так как

- наименьшее?