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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Властивості[ред.ред. код]

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

Приклад[ред.ред. код]

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

Обчислення[ред.ред. код]

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

Додатки[ред.ред. код]

Характери Діріхле[ред.ред. код]

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]