Русская Википедия:Первообразный корень (теория чисел)
Шаблон:Значения Первообразный корень по модулю m ― целое число g такое, что
- <math>g^{\varphi(m)} \equiv 1 \pmod m</math>
и
- <math>g^{\ell} \not\equiv 1 \pmod m</math> при <math>1\le\ell < \varphi(m),</math>
где <math>\varphi(m)</math> ― функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю m.
Чтобы не проверять все <math>\ell</math> от <math>1</math> до <math>\varphi(m)</math>, достаточно проверить три условия:
- Является ли <math>g</math> числом взаимно простым с <math>m</math>, и если нет - то это не первообразный корень.
- Так как <math>\varphi(m)</math> - всегда чётное число для всех <math>m > 2</math>, то <math>\varphi(m)</math> имеет как минимум один простой делитель - простое число <math>2</math>, следовательно, для того, чтобы отсеять значительное количество не-корней, достаточно проверить <math>g^{\varphi(m)/2} \not\equiv 1 \pmod m</math> для числа, подходящего на первообразный корень по модулю <math>m</math>.[1] Если результат +1 <math>\equiv</math> m , то g - не корень, в ином случае результат -1 <math>\equiv</math> m, когда g - это возможно первообразный корень.
- Далее следует убедиться, что <math>g^{\ell} \not\equiv 1 \pmod m</math> для всех <math>\ell = \frac{\varphi(m)}{p}</math>, где <math>p</math> - простой делитель числа <math>\varphi(m)</math>, полученный в результате его факторизации.
Свойства
Существование
Первообразные корни существуют только по модулям <math>m</math> вида
- <math>m=2,4,p^a,2p^a</math>,
где <math>p>2</math> ― простое число, <math>a\geqslant1</math> ― натуральное. Только в этих случаях мультипликативная группа кольца вычетов по модулю m является циклической группой порядка <math>\varphi(m)</math>.
Количество
Если по модулю <math>m</math> существует первообразный корень <math>g</math>, то всего существует <math>\varphi(\varphi(m))</math> различных первообразных корней по модулю m, причём все они имеют вид <math>g^k</math>, где <math>1 \le k < \varphi(m)</math> и <math>(k, \varphi(m)) = 1</math>.
Индекс числа по модулю
Для первообразного корня <math>g</math> его степени <math>g^{\varphi(m)}=1, g, \dots g^{\varphi(m)-1}</math> несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа <math>a</math>, взаимно простого с <math>m</math>, найдется показатель <math>\ell, 0\le\ell<\varphi(m)</math>, такой, что
- <math>g^{\ell} \equiv a \pmod m.</math>
Такое число <math>\ell</math> называется индексом числа a по основанию g.
Минимальный корень
Исследования Виноградова показали, что существует такая константа <math>C</math>, что для всякого простого <math>p</math> существует первообразный корень <math>g<C\sqrt{p}</math>. Другими словами, для простых модулей <math>p</math> минимальный первообразный корень имеет порядок <math>O(\sqrt{p})</math>. Математик Шаблон:Iw из Университета Торонто показал, что если «Обобщённая гипотеза Римана» верна, то первообразный корень есть среди первых <math>O(\log^6 {p})</math> чисел натурального ряда[2].
История
Первообразные корни для простых модулей <math>p</math> были введены Эйлером, но существование первообразных корней для любых простых модулей <math>p</math> было доказано лишь Гауссом в «Арифметических исследованиях» (1801 год).
Примеры
Число 3 является первообразным корнем по модулю 7. Чтобы в этом убедиться, достаточно каждое число от 1 до 6 представить как некоторую степень тройки по модулю 7:
- <math>3^1 \equiv 3\ \pmod 7</math>
- <math>3^2 \equiv 2\ \pmod 7</math>
- <math>3^3 \equiv 6\ \pmod 7</math>
- <math>3^4 \equiv 4\ \pmod 7</math>
- <math>3^5 \equiv 5\ \pmod 7</math>
- <math>3^6 \equiv 1\ \pmod 7</math>
Примеры наименьших первообразных корней по модулю 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 |
См. также
Примечания
Литература
Ссылки
