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

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

Теорема. Первообразный корень по модулю ${\displaystyle m}$ существует, если и только если выполнено одно из условий:

${\displaystyle m=2,\quad m=4,\quad m=p^{a},\quad m=2p^{a},\qquad (1)}$

где ${\displaystyle p}$ – простое нечётное число, ${\displaystyle a}$ – целое, ${\displaystyle a\geq 1}$.

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

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

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

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

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

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

Пример 2. При ${\displaystyle m=7}$ кольцо ${\displaystyle \mathbb {Z} /7\mathbb {Z} }$ является полем, поэтому все элементы, кроме нулевого, обратимы, количество ненулевых элементов равно шести, и они являются вычетами чисел ${\displaystyle 1,2,3,4,5,6}$. Вычет числа ${\displaystyle 3}$ является первообразным корнем по модулю ${\displaystyle 7}$, т. к. вычеты по модулю ${\displaystyle 7}$ первых шести неотрицательных степеней числа ${\displaystyle 3}$ попарно различны:

${\displaystyle {\begin{array}{lll}3^{0}=1{\bmod {7}},&3^{1}=3{\bmod {7}},&3^{2}=9=2{\bmod {7}},\\\\3^{3}=27=6{\bmod {7}},&3^{4}=81=4{\bmod {7}},&3^{5}=243=5{\bmod {7}}.\end{array}}}$

Поскольку число первообразных корней по модулю ${\displaystyle 7}$ равно ${\displaystyle \varphi (\varphi (7))=\varphi (6)=2}$, должен существовать ещё один первообразный корень по модулю ${\displaystyle 7}$. Таким корнем является вычет числа ${\displaystyle 5}$.

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