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

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Определение

Первообразным (примитивным) корнем по модулю n (от английского primitive root modulo n) называется такое число g, что все его степени по модулю n пробегают по всем числам, взаимно простым с n. Математически это формулируется таким образом: если g является первообразным корнем по модулю n, то для любого целого a такого, что {\rm gcd}(a,n)=1, найдётся такое целое k, что g^k \equiv a \pmod{n}.

В частности, для случая простого n степени первообразного корня пробегают по всем числам от 1 до n-1.

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

Первообразный корень по модулю n существует тогда и только тогда, когда n является либо степенью нечётного простого, либо удвоенной степенью простого, а также в случаях n=1, n=2, n=4. (Доказано Гауссом в 1801)


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация