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

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

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

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

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

Властивості

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

Приклад

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

Обчислення

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

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

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

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

Див. також

• Дискретний логарифм
• Функція Кармайкла

Посилання

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