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

(a) Рассмотрим все возможные ненулевые вычеты по модулю Пусть — первообразный корень. Тогда эти вычеты имеют вид Возведем их в степень. Тогда получим набор Заметим, что делится на и частное равно Тогда легко видеть, что Из этого получаем, что сравнение имеет решения для Таким образом, все решения сравнения являются решениями одного из сравнений вида откуда вытекает требуемое.

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

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

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

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

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

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

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