Порядок числа по модулю

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

$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)$.

См. также

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

Литература

• Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
• Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.