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

Пусть для некоторого имеет место сравнение Тогда Пусть Заметим, что Если то сравнение не выполняется, откуда получаем, что Так как (по малой теореме Ферма), то тогда откуда и получаем

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