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

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

${\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}$

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

Щоб показати залежність показника ${\displaystyle \ell }$ від a і m, його також позначають ${\displaystyle P_{m}(a)}$, а якщо m фіксоване, то просто ${\displaystyle P(a)}$.

Властивості

• ${\displaystyle a\equiv b{\pmod {m}}\Rightarrow P(a)=P(b)}$, тому можна вважати, що показник задано на класі лишків ${\displaystyle {\bar {a}}}$ за модулем m.
• ${\displaystyle a^{n}\equiv 1{\pmod {m}}\Rightarrow P(a)\mid n}$. Зокрема, ${\displaystyle P(a)\mid \lambda (m)}$ и ${\displaystyle P(a)\mid \varphi (m)}$, де ${\displaystyle \lambda (m)}$ — ^[en], а ${\displaystyle \varphi (m)}$ — функція Ейлера.
• ${\displaystyle a^{t}\equiv a^{s}{\pmod {m}}\Leftrightarrow t\equiv s{\pmod {P(a)}}.}$
• ${\displaystyle P(a^{s})\mid P(a)}$; якщо ${\displaystyle \gcd(s,P(a))=1}$, то ${\displaystyle P(a^{s})=P(a).}$
• Якщо p — просте число і ${\displaystyle P(a)=k}$, то ${\displaystyle a,\ldots ,a^{k}}$ — всі розв'язки порівняння ${\displaystyle x^{k}\equiv 1{\pmod {p}}}$.
• Якщо p — просте число, то ${\displaystyle P(a)=p-1\Leftrightarrow a}$ — твірна групи ${\displaystyle \mathbb {Z} _{p}}$.
• Якщо ${\displaystyle \psi (k)}$ — кількість класів лишків із показником ${\displaystyle k}$, то ${\displaystyle \sum \limits _{k\mid \varphi (m)}\psi (k)=\varphi (m)}$. А для простих модулів навіть ${\displaystyle \psi (k)=\varphi (k)}$.
• Якщо p — просте число, то група лишків ${\displaystyle \mathbb {Z} _{p}^{\times }}$ циклічна і тому, якщо ${\displaystyle a=g^{dk}}$, де g — твірна, ${\displaystyle d\mid p-1}$, а k взаємно просте із ${\displaystyle p-1}$, то ${\displaystyle P(a)={\frac {p-1}{d}}}$. В загальному випадку для довільного модуля m можна вивести аналогічну формулу, користуючись теоремою про структуру мультиплікативної групи лишків ${\displaystyle \mathbb {Z} _{m}^{\times }}$.

Приклад

Оскільки ${\displaystyle 2^{4}\equiv 1{\pmod {15}}}$, але ${\displaystyle 2^{1}\not \equiv 1{\pmod {15}}}$, ${\displaystyle 2^{2}\not \equiv 1{\pmod {15}}}$, ${\displaystyle 2^{3}\not \equiv 1{\pmod {15}}}$, то порядок числа 2 за модулем 15 дорівнює 4.

Обчислення

Якщо відомий розклад модуля m на прості множники ${\displaystyle p_{j}}$ і відомий розклад чисел ${\displaystyle p_{j}-1}$ на прості множники, то показник заданого числа a може бути знайдений за поліноміальний час від ${\displaystyle \ln m}$. Для обчислення досить знайти розклад на множники функції Кармайкла ${\displaystyle \lambda (m)}$ і обчислити всі ${\displaystyle a^{d}\mod m}$ для всіх ${\displaystyle d\mid \lambda (m)}$. Оскільки число дільників обмежене многочленом від ${\displaystyle \ln m}$, а піднесення до степеня за модулем відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.

Застосування

Характери Діріхле

Характер Діріхле ${\displaystyle \chi }$ за модулем ${\displaystyle m}$ визначається обов'язковими співвідношеннями ${\displaystyle \chi (ab)=\chi (a)\chi (b)}$ і ${\displaystyle \chi (a)=\chi (a+m)}$. Щоб ці співвідношення виконувалися, необхідно, щоб ${\displaystyle \chi (a)}$ дорівнював якомусь комплексному кореню із одиниці степеня ${\displaystyle P_{m}(a)}$.

Див. також

• Дискретний логарифм
• ^[en]

Посилання

• Weisstein, Eric W. Multiplicative Order(англ.) на сайті Wolfram MathWorld.