Первообразный корень по модулю

Определение

Первообразным (примитивным) корнем по модулю $n$ (от английского primitive root modulo n) называется такое число $g$, что все его степени по модулю $n$ пробегают по всем числам, взаимно простым с $n$. Математически это формулируется таким образом: если $g$ является первообразным корнем по модулю $n$, то для любого целого $a$ такого, что ${\rm gcd}(a,n)=1$, найдётся такое целое $k$, что $g^k \equiv a \pmod{n}$.

В частности, для случая простого $n$ степени первообразного корня пробегают по всем числам от $1$ до $n-1$.

Существование

Первообразный корень по модулю $n$ существует тогда и только тогда, когда $n$ является либо степенью нечётного простого, либо удвоенной степенью простого, а также в случаях $n=1, n=2, n=4$. (Доказано Гауссом в 1801)