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

Текущая версия на 11:41, 9 декабря 2013

[править] Определение

Первообразным (примитивным) корнем по модулю $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)

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

Текущая версия на 11:41, 9 декабря 2013

[править] Определение

[править] Существование

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

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация