Подсказку понял, спасибо! Степени будут всегда взаимно просты с

А я подсказку не понял. И степенями будут числа, взаимно простые с

.
Если

-примитивный, то и

- примитивный. Все пары сокращаются кроме редкого случая

.
Действительно, перемудрили с формулировкой. Функция Эйлера всегда чётная, кроме

.
Я из- за такой формулировки про круговой многочлен вспомнил: если

-- все первообразные корни, то

. А свободный член у кругового многочлена равен

. Но это рассуждение только для простого

подходит, когда остатки образуют поле. А Ваше док-во проще и подходит для любого

, для которого существует первобразный корень.