Порядок числа по модулю (Hkjx;kt cnvlg hk bk;rlZ)

Показателем, или мультипликативным порядком, целого числа $a$ по модулю $m$ называется наименьшее положительное целое число $\ell$ , такое, что^[1]^[2]

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

Показатель определен только для чисел $a$ , взаимно простых с модулем $m$ , то есть для элементов группы обратимых элементов кольца вычетов по модулю $m$ . При этом, если показатель числа $a$ по модулю $m$ определен, то он является делителем значения функции Эйлера $\varphi (m)$ (следствие теоремы Лагранжа) и значения функции Кармайкла $\lambda (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)$ .