Первообразный корень (теория чисел)

Шаблон:Значения Первообразный корень по модулю m — целое число g такое, что

$g^{\phi (m)}\equiv 1(\mathrm{mod}m)$

и

$g^{\ell }\equiv ̸1(\mathrm{mod}m)$ при $1⩽\ell <\phi (m),$

где $\phi (m)$ — функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю m.

Чтобы не проверять все $\ell$ от $1$ до $\phi (m)$, достаточно проверить три условия:

1. Является ли $g$ числом взаимно простым с $m$, и если нет, то это не первообразный корень.
2. Так как $\phi (m)$ — всегда чётное число для всех $m>2$, то $\phi (m)$ имеет как минимум один простой делитель — простое число $2$, следовательно, для того, чтобы отсеять значительное количество не-корней, достаточно проверить $g^{\phi (m)/2}\equiv ̸1(\mathrm{mod}m)$ для числа, подходящего на первообразный корень по модулю $m$. Если результат +1 $\equiv$ m, то g — не корень, в ином случае результат −1 $\equiv$ m, когда g — это возможно первообразный корень.
3. Далее следует убедиться, что $g^{\ell }\equiv ̸1(\mathrm{mod}m)$ для всех $\ell =\phi (m)/p$, где $p$ — простой делитель числа $\phi (m)$, полученный в результате его факторизации.

Свойства

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

Первообразные корни существуют только по модулям $m$ вида

$m=2,4,p^a,2p^a$,

где $p>2$ ― простое число, $a⩾1$ ― натуральное. Только в этих случаях мультипликативная группа кольца вычетов по модулю m является циклической группой порядка $\phi (m)$.

Количество

Если по модулю $m$ существует первообразный корень $g$, то всего существует $\phi (\phi (m))$ различных первообразных корней по модулю m, причём все они имеют вид $g^k(\mathrm{mod}m)$, где $1\le k<\phi (m)$ и $(k,\phi (m))=1$.

Индекс числа по модулю

Для первообразного корня $g$ его степени $g^{\phi (m)}=1,g,\dots g^{\phi (m)-1}$ несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа $a$, взаимно простого с $m$, найдется показатель $\ell ,1\le \ell \le \phi (m)$, такой, что

$g^{\ell }\equiv a(\mathrm{mod}m).$

Такое число $\ell$ называется индексом числа a по основанию g.

Минимальный корень

Исследования Виноградова показали, что существует такая константа $C$, что для всякого простого $p$ существует первообразный корень $g<C\sqrt{p}$. Другими словами, для простых модулей $p$ минимальный первообразный корень имеет порядок $O(\sqrt{p})$. Математик Шаблон:Iw из Университета Торонто показал, что если «Обобщённая гипотеза Римана» верна, то первообразный корень есть среди первых $O({\log }^{6}p)$ чисел натурального ряда.

История

Первообразные корни для простых модулей $p$ были введены Эйлером, но существование первообразных корней для любых простых модулей $p$ было доказано лишь Гауссом в «Арифметических исследованиях» (1801 год).

Примеры

Число 3 является первообразным корнем по модулю 7. Чтобы в этом убедиться, достаточно каждое число от 1 до 6 представить как некоторую степень тройки по модулю 7:

$3^1\equiv 3(\mathrm{mod}7)$

$3^2\equiv 2(\mathrm{mod}7)$

$3^3\equiv 6(\mathrm{mod}7)$

$3^4\equiv 4(\mathrm{mod}7)$

$3^5\equiv 5(\mathrm{mod}7)$

$3^6\equiv 1(\mathrm{mod}7)$

Примеры наименьших первообразных корней по модулю m (Шаблон:OEIS):

Модуль m	2	3	4	5	6	7	8	9	10	11	12	13	14
Первообразный корень	1	2	3	2	5	3	—	2	3	2	—	2	3

См. также

• Гипотеза Артина
• Дискретное логарифмирование
• Показатель числа по модулю

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

• «Первообразные корни» на сайте MAXimal Шаблон:Wayback
• Шаблон:H