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

Февраль 24, 2021 / Комментарии 0

Первообразный корень по модулю 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):

    Подпишитесь на свежую email рассылку сайта!

    Читайте также