Turbo: Новая страница: «== Определение == Первообразным (примитивным) корнем по модулю $n$ (от английского ''prim…»

2013-12-09T08:41:03Z

Новая страница: «== Определение == Первообразным (примитивным) корнем по модулю <math>n</math> (от английского ''prim…»

Новая страница

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

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

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

Первообразный корень по модулю - История изменений

Turbo: Новая страница: «== Определение == Первообразным (примитивным) корнем по модулю n (от английского ''prim…»

Turbo: Новая страница: «== Определение == Первообразным (примитивным) корнем по модулю $n$ (от английского ''prim…»