Понятно, что

делит

Но для нечётного

, пользуясь биномом Ньютона, имеем:
и поэтому

не может делить
Если же

то

и в этом случае имеем контр-пример к условию задачи.
Кстати, как видно из вышесказанного, простота

здесь роли не играет - важна только нечётность

. Хотя для чётного

все тоже легко доказывается.