WikiSort.ru - Не сортированное

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

${\displaystyle g^{\varphi (m)}\equiv 1{\pmod {m}}}$

и

${\displaystyle g^{\ell }\not \equiv 1{\pmod {m}}}$ при ${\displaystyle 1\leq \ell <\varphi (m),}$

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

Свойства

История

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

Примеры

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

${\displaystyle 3^{0}\equiv 1\ {\pmod {7}}}$

${\displaystyle 3^{1}\equiv 3\ {\pmod {7}}}$

${\displaystyle 3^{2}\equiv 2\ {\pmod {7}}}$

${\displaystyle 3^{3}\equiv 6\ {\pmod {7}}}$

${\displaystyle 3^{4}\equiv 4\ {\pmod {7}}}$

${\displaystyle 3^{5}\equiv 5\ {\pmod {7}}}$

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

См. также

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

Ссылки

• «Первообразные корни» на сайте MAXimal

Литература

• Виноградов И. М. Глава 6. Первообразные корни и индексы // Основы теории чисел. — 1952. — 182 с.
• Нестеренко Ю. В. Глава 7. Первообразные корни и индексы // Теория чисел. — М.: «Академия», 2008. — 464 с.