Вопрос про вычеты (группа (Z/nZ)*)

[Юстас]

Возник такой вопрос: пусть $p$ - простое число. Всегда ли в системе наименьших положительных вычетов $(1,2,...,p-1)$ найдется элемент $q$, такой что $(p-1)$-наименьшая степень, для которой верно $q^N\equiv 1(mod\ p\ )$?

[Руст]

Да. Это следует из того, что $(Z/pZ)^*$ циклическая группа. Вообще группа $(Z/nZ)^* циклична только в случаях, когда $n=2,4,p^k,2p^k$, где р нечётное простое число.

[Юстас]

Известно ли Вам простое доказательство, методами элементарной теории чисел? Я сходу придумать не смог.

[Руст]

Суть в двух словах в подсчёте числа обратимых элементов в поле из р элементов. Так как в поле р-1 обратимых элементов, то по теореме Лагранжа р-1 -ая степень равна 1 для обратимых, а значит все элементы поля корни уравнения $z^p=z$. Если бы мультипликативная группа вычетов была бы нециклической, то наименьший общий порядок k был бы меньше p-1 (был бы его делителем) и мы бы получили, что уравнение $x^k-1=0$ имело бы p-1>k корней, что невозможно в поле.
Есть и другие доказательства в учебниках по теории чисел и близких к нему.