Показатели и первообразные корни

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

Пусть теперь для некоторого имеем Тогда Если теперь взаимно просто с то очевидно, что — показатель Итак, является первообразным корнем тогда и только тогда, когда а потому количество первообразных корней равно количеству подходящих то есть

(b) Пусть — первообразный корень. Любой вычет имеет вид Попробуем найти критерий того, что где Пусть и Тогда то есть тогда Пусть Предположим, что Тогда и получае, что откуда Тогда поэтому показатель не меньше а, с другой стороны, степень дает остаток 1.

Предположим, что Тогда а потому не может являться показателем. Итак, равносильно и Чтобы подсчитать количество подходящих вычетов, достаточно найти количество чисел взаимно простых с Это в точности