Неприводимость и разложение на неприводимые многочлены

Будем воспринимать данный набор чисел, как набор ненулевых остатков по модулю Так как число — простое, то существует первообразный корень по модулю Пусть — некоторый первообразный корень по модулю Пусть Заметим, что — по малой теореме Ферма. Преобразуем это сравнение:

Заметим, что так как — первообразный корень. Это значит, что

Тогда разделим все числа на групп вида где некоторый ненулевой остаток по модулю Проверим, что сумма этих чисел делится на

Теперь покажем, что все числа различны. Допустим, что два числа совпали внутри группы. Тогда имеем

Тогда получаем, что Будем считать, что Тогда, так как — простое, имеем При этом тогда Так как — простое, то но это противоречит тому, что первообразный корень.

Допустим, теперь, что числа из разных групп совпали. Это эквивалентно сравнению Но тогда мы получаем, что то есть — число из группы однако мы предполагали, что числа из разных групп — противоречие.

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