Первообразный корень (теория чисел)

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

g φ ( m ) ≡ 1 ( mod m ) {displaystyle g^{varphi (m)}equiv 1{pmod {m}}}

g ℓ ≢ 1 ( mod m ) {displaystyle g^{ell }
ot equiv 1{pmod {m}}} при 1 ≤ ℓ < φ ( m ) , {displaystyle 1leq ell <varphi (m),}

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

Чтобы не проверять все ℓ {displaystyle ell } от 1 {displaystyle 1} до φ ( m ) {displaystyle varphi (m)} , достаточно проверить три условия:

Является ли g {displaystyle g} числом взаимно-простым с m {displaystyle m} , и если нет — то это не первообразный корень.

Так как φ ( m ) {displaystyle varphi (m)} , всегда число четное, для всех чисел m > 2 {displaystyle m>2} , то φ ( m ) {displaystyle varphi (m)} имеет как минимум один простой делитель — простое число 2 {displaystyle 2} , то следовательно, для того, чтобы отсеять значительное количество не-корней, достаточно проверить g φ ( m ) / 2 ≢ 1 ( mod m ) {displaystyle g^{varphi (m)/2}
ot equiv 1{pmod {m}}} для числа, походящего на первообразный корень по модулю m {displaystyle m} . Если результат — 1, то g — не корень, если результат φ ( m ) {displaystyle varphi (m)} , то g — это возможно-первообразный корень.

Далее, следует убедиться, что g ℓ ≢ 1 ( mod m ) {displaystyle g^{ell }
ot equiv 1{pmod {m}}} , для всех ℓ = φ ( m ) p {displaystyle ell ={frac {varphi (m)}{p}}} , где p {displaystyle p} — простой делитель числа φ ( m ) {displaystyle varphi (m)} , полученный в результате его факторизации.

Свойства

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

Первообразные корни существуют только по модулям m {displaystyle m} вида

m = 2 , 4 , p a , 2 p a {displaystyle m=2,4,p^{a},2p^{a}} ,

где p > 2 {displaystyle p>2} ― простое число, a ⩾ 1 {displaystyle ageqslant 1} ― целое. Только в этих случаях мультипликативная группа кольца вычетов по модулю m является циклической группой порядка φ ( m ) {displaystyle varphi (m)} .

Индекс числа по модулю

Для первообразного корня g его степени g0=1, g, …, gφ(m) − 1 несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа a, взаимно простого с m, найдется показатель ℓ, 0 ⩽ ℓ ⩽ φ(m) − 1, такой, что

g ℓ ≡ a ( mod m ) . {displaystyle g^{ell }equiv a{pmod {m}}.}

Такое число ℓ называется индексом числа a по основанию g.

Количество

Если по модулю m существует первообразный корень g, то всего существует φ(φ(m)) различных первообразных корней по модулю m, причём все они имеют вид g k {displaystyle g^{k}} , где 1 ≤ k ≤ φ ( m ) − 1 {displaystyle 1leq kleq varphi (m)-1} и ( k , φ ( m ) ) = 1 {displaystyle (k,varphi (m))=1} .

Минимальный корень

Исследования Виноградова показали, что существует такая константа C {displaystyle C} , что для всякого простого p {displaystyle p} существует первообразный корень g < C p {displaystyle g<C{sqrt {p}}} . Другими словами, для простых модулей p {displaystyle p} минимальный первообразный корень имеет порядок O ( p ) {displaystyle O({sqrt {p}})} . Математик Виктор Шуп из Университета Торонто показал, что если «Обобщённая гипотеза Римана» верна, то первообразный корень есть среди первых O ( log 6 ⁡ p ) {displaystyle O(log ^{6}{p})} чисел натурального ряда.

История

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

Примеры

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

3 1 ≡ 3 ( mod 7 ) {displaystyle 3^{1}equiv 3 {pmod {7}}} 3 2 ≡ 2 ( mod 7 ) {displaystyle 3^{2}equiv 2 {pmod {7}}} 3 3 ≡ 6 ( mod 7 ) {displaystyle 3^{3}equiv 6 {pmod {7}}} 3 4 ≡ 4 ( mod 7 ) {displaystyle 3^{4}equiv 4 {pmod {7}}} 3 5 ≡ 5 ( mod 7 ) {displaystyle 3^{5}equiv 5 {pmod {7}}} 3 6 ≡ 1 ( mod 7 ) {displaystyle 3^{6}equiv 1 {pmod {7}}}

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