Показник числа за модулем

Показником, або мультиплікативним порядком, цілого числа a за модулем m називається найменше додатне ціле число , таке, що

Показник визначений тільки для чисел a, взаємно простих за модулем m, тобто для елементів групи оборотних елементів кільця лишків за модулем m. При цьому, якщо показник числа a за модулем визначений, то він є дільником значення функції Ейлера (наслідок теореми Лагранжа).

Щоб показати залежність показника від a і m, його також позначають , а якщо m фіксоване, то просто .

ВластивостіРедагувати

  •  , тому можна вважати, що показник задано на класі лишків   за модулем m.
  •  . Зокрема,   и  , де   — функція Кармайкла[en], а   — функція Ейлера.
  •  
  •  ; якщо  , то  
  • Якщо p — просте число і  , то   — всі розв'язки порівняння  .
  • Якщо p — просте число, то   — твірна групи  .
  • Якщо   — кількість класів лишків із показником  , то  . А для простих модулів навіть  .
  • Якщо p — просте число, то група лишків   циклічна і тому, якщо  , де g — твірна,  , а k взаємно просте із  , то  . В загальному випадку для довільного модуля m можна вивести аналогічну формулу, користуючись теоремою про структуру мультиплікативної групи лишків  .

ПрикладРедагувати

Оскільки  , але  ,  ,  , то порядок числа 2 за модулем 15 дорівнює 4.

ОбчисленняРедагувати

Якщо відомий розклад модуля m на прості множники   і відомий розклад чисел   на прості множники, то показник заданого числа a може бути знайдений за поліноміальний час від  . Для обчислення досить знайти розклад на множники функції Кармайкла   і обчислити всі   для всіх  . Оскільки число дільників обмежене многочленом від  , а піднесення до степеня за модулем відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.

ЗастосуванняРедагувати

Характери ДіріхлеРедагувати

Характер Діріхле   за модулем   визначається обов'язковими співвідношеннями   і  . Щоб ці співвідношення виконувалися, необхідно, щоб   дорівнював якомусь комплексному кореню із одиниці степеня  .

Див. такожРедагувати

ПосиланняРедагувати