Ввиду отсутствия постов в теме, все либо думают что задача слишком сложна, либо, что автор (т.е. я) ошибся и нашел неправильное решение.
Поэтому, чтоб было интереснее и исключить двусмысленности, дам небольшую подсказку:
Для решения задачи необходимо рассмотреть три случая:
1. Либо

, либо

.
2.

.
3.

.
Первый случай уже рассмотрен
mihiv выше.
Случай 2:
1. Пусть

- нечетно и делится на

. Тогда

2. Поскольку

- нечетно, то числа в правой части взаимно просты, а поэтому являются также

-степенями:

3. Решая систему первых двух уравнений, находим:

поэтому, если

не делится на

, то

по малой теореме Ферма. Но тогда и

также делится на

. Поэтому

.
На этом подсказка окончена.
