Первообра́зный ко́рень по мо́дулю $m,$ элемент $g$ кольца $\mathbb Z/m\mathbb Z$ вычетов по модулю $m,$ такой, что любой обратимый элемент кольца $\mathbb Z/m\mathbb Z$ является некоторой степенью элемента $g.$ Первообразный корень $g$ по модулю $m,$ будучи элементом факторкольца, может быть записан как смежный класс $G+m\mathbb Z$ некоторого целого числа $G,$ удовлетворяющего неравенствам $1<G<m.$ Допуская вольность речи, иногда называют первообразным корнем по модулю $m$ целое число $G,$ а не его вычет по модулю $m.$ Если для данного $m$ первообразный корень $g$ по модулю $m$ существует, то мультипликативная группа $U(\mathbb Z/m\mathbb Z)$ обратимых элементов кольца $\mathbb Z/m\mathbb Z$ является циклической, а $g$ является образующим элементом этой группы.

Теорема. Первообразный корень по модулю $m$ существует, если и только если выполнено одно из условий:$$m=2,\quad m=4,\quad m=p^a,\quad m=2p^a,\qquad(1)$$где $p$ – простое нечётное число, $a$ – целое, $a \ge1.$

Определение первообразного корня по модулю впервые было дано немецким математиком И. Г. Ламбертом в 1769 г. Стремясь найти критерии простоты натурального числа $p$ и способы разложения составного $p$ на множители, Ламберт изучал представления рациональных чисел вида $1/p$ в виде бесконечных десятичных периодических дробей. Ламберт доказал с помощью малой теоремы Ферма, что если десятичное разложение дроби $1/p$ периодично с периодом $m,$ то $m$ делит $p-1,$ и предположил, что если $m$ имеет максимально возможное значение $p-1,$ то число $10$ является первообразным корнем по модулю $m.$ В работе 1801 г. немецкий математик К. Ф. Гаусс доказал справедливость этого утверждения Ламберта и доказал общую теорему о том, что первообразные корни по модулю p существуют для любого простого p. Впервые доказательство этой общей теоремы опубликовал в 1773 г. российский академик Л. Эйлер, однако доказательство не было дано им в достаточно чёткой форме.

Эквивалентное определение первообразного корня по модулю $m.$ Известно, что вычет $x+m\mathbb Z$ целого числа $x$ является обратимым в кольце $\mathbb Z/m\mathbb Z,$ если и только если $x$ и $m$ взаимно просты, поэтому число обратимых элементов кольца $\mathbb Z/m\mathbb Z$ равно количеству натуральных чисел, меньших $m$ и взаимно простых с $m.$ Это количество принято обозначать $\varphi(m),$ где $\varphi$ называется функцией Эйлера (англ. Euler‘s totient function). Если $g$ является первообразным корнем по модулю $m,$ то

вычеты $g^0, g^1, g^2, \ldots , g^{\varphi(m)-1}$ попарно различны и $g^{\varphi(m)}=1+m\mathbb Z.\qquad(2)$

Обратно, если выполнено условие $(2),$ то вычет $g$ является первообразным корнем по модулю $m.$

Количество первообразных корней по модулю $m.$ Известно, что если $x$ – некоторый образующий элемент циклической мультипликативной группы порядка $n,$ то элемент $x^k$ будет образующим, если и только если $n$ и $k$ взаимно просты. Поэтому число образующих элементов циклической группы порядка $n$ равно $\varphi(n).$ Применяя это утверждение к группе обратимых элементов кольца $\mathbb Z/m\mathbb Z,$ получаем, что при выполнении одного из условий $(1)$ число первообразных корней по модулю $m$ равно $\varphi(\varphi(m)).$

Пример 1. При $m=2$ группа обратимых элементов кольца $\mathbb Z/2\mathbb Z$ состоит из одного элемента, является циклической и порождается вычетом числа $1,$ который является единственным первообразным корнем по модулю $2.$

Пример 2. При $m=7$ кольцо $\mathbb Z/7\mathbb Z$ является полем, поэтому все элементы, кроме нулевого, обратимы, количество ненулевых элементов равно шести, и они являются вычетами чисел $1, 2, 3, 4, 5, 6.$ Вычет числа $3$ является первообразным корнем по модулю $7,$ т. к. вычеты по модулю $7$ первых шести неотрицательных степеней числа $3$ попарно различны:$$\begin{array}{lll} 3^0=1\bmod7,&3^1=3\bmod7,&3^2=9=2\bmod7,\\ \\ 3^3=27=6\bmod7,&3^4=81=4\bmod7,&3^5=243=5 \bmod7. \end{array}$$Поскольку число первообразных корней по модулю $7$ равно $\varphi(\varphi(7)) =\varphi(6)=2,$ должен существовать ещё один первообразный корень по модулю $7.$ Таким корнем является вычет числа $5.$

Пример 3. При $m=8$ обратимыми элементами кольца $\mathbb Z/8\mathbb Z$ являются вычеты нечётных чисел $1, 3, 5, 7$ и группа обратимых элементов имеет порядок $4.$ Квадрат каждого из чисел $1, 3, 5, 7$ сравним с $1$ по модулю $8;$ поэтому группа обратимых элементов кольца $\mathbb Z/8\mathbb Z$ не является циклической и, значит, первообразных корней по модулю $8$ не существует.