Необходимость

Пусть p - простое.

Способ 1.

Рассмотрим . Множество ненулевых классов классов вычетов по простому модулю p по умножению является группой, и тогда - это произведение всех элементов группы . Поскольку - группа, то для каждого ее элемента существует единственный обратный элемент . Соответствие разбивает группу на классы: если (что равносильно ), то класс содержит один элемент , в противном случае класс состоит из двух элементов - . Значит, если класс содержит один элемент , то произведение всех его элементов равно , а если класс содержит 2 элемента, то произведение всех его элементов равно 1. Теперь в произведении сгруппируем элементы по классам, все произведения по 2-хэлементным классам просто равны 1:

■

Способ 2.

Группа циклична, т.е. существует элемент такой, что для всякого элемента существует такое, что . Поскольку имеет элемент, то пробегает значения от 0 до , когда пробегает всю группу вычетов. Тогда

■

Способ 3.

- поле, поэтому в нем имеет место теорема Безу, т.е. многочлен степени имеет не более корней. Рассмотрим многочлены и . Оба многочлена имеют корни (для это получается по малой теореме Ферма), степени многочленов равны , старшие коэффициенты одинаковы. Тогда многочлен имеет как минимум те же корней, но его степень не более . Значит по теореме Безу тождественно равен нулю, т.е. для всех будет , в частности , что равносильно . Получаем утверждение теоремы для , т.к. четно и значит .■

Достаточность

Если составное и , то , а при получаем .